Задача об упаковке в контейнеры: различия между версиями

Константа 1,691 возникает и во многих других контекстах упаковки в контейнеры. Обычно она обозначается <math>h_{\infty}</math> и равна <math>\sum_{i = 1}^{\infty} (1/t_i)</math>, где <math>t_1 = 1</math>, а для i > 1 <math>t_i = t_{i - 1}(t_{i - 1} + 1)</math>. Нижняя граница в Теореме 8 является строгой благодаря существованию алгоритмов ''Нarmonic''<math>_k</math> (<math>H_k</math>) из [17]. <math>H_k</math> – это алгоритм, основанный на классах, в котором предметы делятся на классы <math>C_h, 1 \le h \le k</math>, причем <math>C_k</math> состоит из всех предметов размером 1/k или меньше, а <math>C_h, 1 \le h < k</math>, состоит из всех <math>a_i</math>, таких, что <math>1/(h + 1) < s(a_i) \le 1/h</math>. Затем предметы каждого класса упаковываются NF в отдельную упаковку, предназначенную только для этого класса. Таким образом, в любой момент времени открыто не более k контейнеров. В [17] было показано, что <math>lim_{k \to \infty} R^{\infty}_{H_k} = h_{\infty} = 1,691...</math> Это даже лучше, чем асимптотическое наихудшее соотношение 1,7 для алгоритмов FF и BF, работающих с неограниченным количеством контейнеров, хотя следует отметить, что вариант BF с ограниченным их количеством, в котором все контейнеры, кроме двух наиболее полных, закрыты, также имеет <math>R^{\infty}_A = 1,7</math>.

Задача об упаковке в контейнеры также послужила ранним испытательным полигоном для изучения поведения аппроксимационных алгоритмов в среднем случае. Пусть F – распределение на интервале (0, 1], а <math>L_n</math> – список из n элементов с размерами элементов, выбранными независимо в соответствии с распределением F. Для любого списка L обозначим за s(L) нижнюю границу OPT(L), полученную суммированием размеров всех элементов в L. Тогда определим

'''Теорема 9 [16, 20]. Для <math>A \in \{ FFD, BFD, OPT \}</math> выполняется <math>EW^n_A(U(0, 1]) = \Theta(\sqrt{n}).</math>