4431
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 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>. Вышеописанный процесс повторяется на протяжении нескольких шагов. На каждом шаге размер остаточного экземпляра уменьшается не менее чем в два раза, а количество контейнеров, необходимых для упаковки | '''Доказательство'''. Пусть <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) дополнительных контейнеров. □ | ||
Остается описать процедуру округления. Рассмотрим элементы в неубывающем порядке | Остается описать процедуру округления. Рассмотрим элементы в неубывающем порядке <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. Если все размеры элементов не меньше | '''Следствие 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> – константа. | ||
== Применение == | == Применение == |
правка