4431
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 33: | Строка 33: | ||
Теорема 2 [4]. Для экземпляра задачи I существует алгоритм, который производит упаковку I с использованием OPT(I) + O( | '''Теорема 2 [4]. Для экземпляра задачи <math>I</math> существует алгоритм, который производит упаковку <math>I</math> с использованием <math>OPT(I) + O(log^2 \; OPT(I))</math> контейнеров. Время выполнения этого алгоритма составляет <math>O(n^8)</math>.''' | ||
Обратите внимание, что эта гарантия значительно сильнее, чем в работе [ ], так как в нее входит аддитивный член O( | Обратите внимание, что эта гарантия значительно сильнее, чем в работе [3], так как в нее входит аддитивный член <math>O(log^2 \; OPT)</math>, а не <math>O(\epsilon \cdot OPT)</math>. В этом алгоритме также используется идея уменьшения количества различных размеров элементов и игнорирования маленьких элементов, но гораздо более тонким образом. В частности, вместо того чтобы получить округленный экземпляр за один шаг, алгоритм состоит из логарифмического числа шагов, на каждом из которых авторы «слегка» округляют экземпляр, а затем частично решают его. | ||
Отправной точкой является экспоненциально большая релаксация линейного программирования (LP) данной задачи, обычно называемая конфигурационной линейной программой. Здесь имеется переменная | Отправной точкой является экспоненциально большая релаксация линейного программирования (LP) данной задачи, обычно называемая конфигурационной линейной программой. Здесь имеется переменная <math>x_S</math>, соответствующая каждому подмножеству предметов S, которые можно подходящим образом упаковать в контейнер. Задача состоит в минимизации <math>\sum_S x_S</math> при условии, что для каждого предмета i сумма <math>x_S</math> по всем подмножествам S, содержащим i, не меньше 1. Очевидно, что это релаксация, поскольку задание соотношения <math>x_S = 1</math> для каждого набора S, соответствующего контейнеру в оптимальном решении, является допустимым целочисленным решением задачи LP. Несмотря на то, что в этой формулировке решение имеет экспоненциальный размер, задача разделения для двойственной формулировки является задачей о рюкзаке, и поэтому LP может быть решена за полиномиальное время с любой точностью (в частности, с точностью до 1) методом эллипсоидов. Такое решение называется дробно-линейной упаковкой. Заметим, что если имеется <math>n_i</math> предметов, каждый из которых имеет размер ровно <math>s_i</math>, то ограничения, соответствующие i, можно «объединить», чтобы получить следующий вариант LP: | ||
<math>min \sum_S x_S</math>, такой, что <math>\sum_S a_{S, i} x_S \ge n_i \; \forall</math> размеров предметов i, <math>x_S \ge 0 \; \forall</math> допустимых множеств S. | |||
правка