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

Перейти к навигации Перейти к поиску
Строка 50: Строка 50:




'''Доказательство'''. Пусть <math>I_0 = I</math> и пусть <math>I_1</math> – экземпляр, полученный в результате применения процедуры округления к <math>I_0</math>. Согласно свойству процедуры округления, <math>OPT(I) \le OPT(I_1) + c</math> и <math>LP(I_1) \le LP(I)</math>. Поскольку в <math>I_1</math> имеется <math>Size(I_0)/2</math> различных размеров, решение LP для <math>I_1</math> имеет не более <math>Size(I_0)/2</math> дробно заданных переменных. Удалим элементы, упакованные в LP-решении цельным образом, и рассмотрим остаточный экземпляр <math>I'_1</math>. Заметим, что <math>Size(I'_1) \le Size(I_0)/2</math>. Теперь заново применим процедуру округления к <math>I'_1</math>, чтобы получить <math>I_2</math>, и решим задачу LP для <math>I_2</math>. И вновь это решение имеет не более <math>Size(I'_1)/2 \le Size(I_0)/4</math> дробно заданных переменных, при этом <math>OPT(I'_1) \le OPT(I_2) + c</math> и <math>LP(I_2) \le LP(I'_1)</math>. Вышеописанный процесс повторяется на протяжении нескольких шагов. На каждом шаге размер остаточного экземпляра уменьшается не менее чем в два раза, а количество контейнеров, необходимых для упаковки I0, увеличивается на аддитивную величину c. После log(Size(I0)) (?rf log(OPT(I))) шагов остаточный экземпляр имеет размер O(1) и может быть упакован в O(1) дополнительных контейнеров. □
'''Доказательство'''. Пусть <math>I_0 = I</math> и пусть <math>I_1</math> – экземпляр, полученный в результате применения процедуры округления к <math>I_0</math>. Согласно свойству процедуры округления, <math>OPT(I) \le OPT(I_1) + c</math> и <math>LP(I_1) \le LP(I)</math>. Поскольку в <math>I_1</math> имеется <math>Size(I_0)/2</math> различных размеров, решение LP для <math>I_1</math> имеет не более <math>Size(I_0)/2</math> дробно заданных переменных. Удалим элементы, упакованные в LP-решении цельным образом, и рассмотрим остаточный экземпляр <math>I'_1</math>. Заметим, что <math>Size(I'_1) \le Size(I_0)/2</math>. Теперь заново применим процедуру округления к <math>I'_1</math>, чтобы получить <math>I_2</math>, и решим задачу LP для <math>I_2</math>. И вновь это решение имеет не более <math>Size(I'_1)/2 \le Size(I_0)/4</math> дробно заданных переменных, при этом <math>OPT(I'_1) \le OPT(I_2) + c</math> и <math>LP(I_2) \le LP(I'_1)</math>. Вышеописанный процесс повторяется на протяжении нескольких шагов. На каждом шаге размер остаточного экземпляра уменьшается не менее чем в два раза, а количество контейнеров, необходимых для упаковки <math>I_0</math>, увеличивается на аддитивную величину <math>c</math>. После <math>log(Size(I_0)) (\approx log(OPT(I)))</math> шагов остаточный экземпляр имеет размер O(1) и может быть упакован в O(1) дополнительных контейнеров. □




Остается описать процедуру округления. Рассмотрим элементы в неубывающем порядке s1 > s2 > … > sn и сгруппируем их следующим образом. Добавляем элементы в текущую группу до тех пор, пока ее размер впервые не превысит 2. В этот момент закрываем группу и начинаем новую. Обозначим за G1... Gk сформированные группы и положим ni = jGij, для удобства задав щ = 0. Определим I0 как экземпляр, полученный округлением размера "i_i наибольших элементов в Gi до размера наибольшего элемента в Gi для i = 1; : : : ; k. Процедура удовлетворяет свойствам леммы 3 при c = O(log щ). Для доказательства Теоремы 2 достаточно показать, что щ = O(Size(I)). Это легко сделать, игнорируя все элементы меньше 1/Size(I) и заполняя их только в конце (подобно алгоритму де ла Веги и Люкера).
Остается описать процедуру округления. Рассмотрим элементы в неубывающем порядке <math>s_1 \ge s_2 \ge ... \ge s_n</math> и сгруппируем их следующим образом. Добавляем элементы в текущую группу до тех пор, пока ее размер впервые не превысит 2. В этот момент закрываем группу и начинаем новую. Обозначим за <math>G_1, ..., G_k</math> сформированные группы и положим <math>n_i = |G_i|</math>, для удобства задав <math>n_0 = 0</math>. Определим <math>I'</math> как экземпляр, полученный округлением размера <math>n_{i - 1}</math> наибольших элементов в <math>G_i</math> до размера наибольшего элемента в <math>G_i</math> для i = 1, ..., k. Процедура удовлетворяет свойствам леммы 3 при <math>c = O(log \; n_k)</math>. Для доказательства Теоремы 2 достаточно показать, что <math>n_k = O(Size(I))</math>. Это легко сделать, игнорируя все элементы меньше 1/Size(I) и заполняя их только в конце (подобно алгоритму де ла Веги и Люкера).




Строка 59: Строка 59:




Следствие 1. Если все размеры элементов не меньше S, то легко видеть, что c = O(log 1/(5), и приведенный выше алгоритм гарантирует OPT+ 0(log(l/<5) -logOPT), что соответствует OPT+ O(logOPT), если S – константа.
'''Следствие 1'''. Если все размеры элементов не меньше <math>\delta</math>, то легко видеть, что <math>c = O(log \; 1 / \delta)</math>, и приведенный выше алгоритм гарантирует <math>OPT+ O(log(1  / \delta) \cdot log \; OPT)</math>, что соответствует <math>OPT+ O(log \; OPT)</math>, если <math>\delta</math> – константа.


== Применение ==
== Применение ==
Источник — http://pco.iis.nsk.su/wega/index.php/Аппроксимационные_схемы_для_задачи_об_упаковке_в_контейнеры