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

'''Теорема 1 [3]. Для любого произвольного параметра <math>\epsilon > 0</math> существует алгоритм, использующий <math>(1 + \epsilon)OPT(I) + O(1)</math> контейнеров для упаковки набора <math>I</math>. Время работы этого алгоритма составляет <math>O(n \; log \; n) + (1 / \epsilon)^{O(1 / \epsilon)}</math>.'''

Подход де ла Веги и Люкера [3] заключался в том, чтобы предложить технику аппроксимации исходного экземпляра более простым экземпляром, в котором крупные предметы могут иметь только O(1) различных размеров. Их идея была проста. Во-первых, достаточно ограничить внимание крупными предметами, скажем, размером больше <math>\varepsilon</math>. Обозначим эту новую задачу <math>I_b</math>. Пусть имеется (почти) оптимальная упаковка для <math>I_b</math>; рассмотрим решение, полученное путем жадного заполнения контейнеров оставшимися мелкими предметами, открывая новые контейнеры только в случае необходимости. Действительно, если новые контейнеры не потребуются, то решение по-прежнему остается почти оптимальным, поскольку упаковка для <math>I_b</math> была почти оптимальной. Если же дополнительные контейнеры необходимы, то каждый контейнер (возможно, за исключением одного) должен быть заполнен до объема <math>(1 - \epsilon)</math>, что дает упаковку с использованием <math>Size(I)/(1 - \epsilon) + 1 \le OPT(I)/(1 - \epsilon) + 1</math> контейнеров. таким образом, достаточно сосредоточиться на решении задачи <math>I_b</math> почти оптимальным образом. Для этого авторы показывают, как получить другой экземпляр задачи <math>I'</math> со следующими свойствами. Во-первых, в <math>I'</math> имеется только <math>O(1 / \epsilon^2)</math> различных размеров, во-вторых, <math>I_b</math>I0 является приближением <math>I_b</math> в том смысле, что <math>OPT(I_b) \ge OPT(I')</math> – и, более того, любое решение <math>I'</math> подразумевает решение <math>I_b</math> с использованием <math>O(\epsilon \cdot OPT(I))</math> дополнительных контейнеров. Поскольку в задаче <math>I'</math> имеется только <math>1 / \epsilon^2</math> различных размеров элементов, а в любой контейнер можно поместить не более <math>1 / \epsilon</math> таких элементов, существует не более <math>O(1 / \epsilon^2)^{1 / \epsilon}</math> способов упаковки в контейнеры. Таким образом, задача <math>I'</math> может быть решена оптимально путем исчерпывающего перечисления (или еще более эффективно с помощью описанной ниже формулировки целочисленного программирования).

Позже Кармаркар и Карп [4] доказали существенно более сильную гарантию.

Теорема 2 [4]. Для экземпляра задачи I существует алгоритм, который производит упаковку I с использованием OPT(I) + O(log2 OPT(I)) контейнеров. Время исполнения этого алгоритма составляет O(n8).