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

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

Обратите внимание, что эта гарантия значительно сильнее, чем в работе [ ], так как в нее входит аддитивный член O(log2 OPT), а не O(e - OPT). В этом алгоритме также используется идея уменьшения количества различных размеров элементов и игнорирования маленьких элементов, но гораздо более тонким образом. В частности, вместо того чтобы получить округленный экземпляр за один шаг, алгоритм состоит из логарифмического числа шагов, на каждом из которых авторы «слегка» округляют экземпляр, а затем частично решают его.

Отправной точкой является экспоненциально большая релаксация линейного программирования (LP) данной задачи, обычно называемая конфигурационной линейной программой. Здесь имеется переменная xS, соответствующая каждому подмножеству товаров S, которые можно подходящим образом упаковать в контейнер. Задача состоит в минимизации PS xS при условии, что для каждого предмета i сумма xS по всем подмножествам S, содержащим i, не меньше 1. Очевидно, что это релаксация, поскольку задание соотношения xS = 1 для каждого набора S, соответствующего контейнеру в оптимальном решении, является допустимым целочисленным решением задачи LP. Несмотря на то, что в этой формулировке решение имеет экспоненциальный размер, задача разделения для двойственной формулировки является задачей о рюкзаке, и поэтому LP может быть решена за полиномиальное время с любой точностью (в частности, с точностью до 1) методом эллипсоидов. Такое решение называется дробно-линейной упаковкой. Заметим, что если имеется ni предметов, каждый из которых имеет размер ровно si, то ограничения, соответствующие i, можно «объединить», чтобы получить следующий вариант LP: