4430
правок
Аппроксимационные схемы для задачи об упаковке в контейнеры: различия между версиями
Материал из WEGA
Аппроксимационные схемы для задачи об упаковке в контейнеры (посмотреть исходный код)
Версия от 20:35, 12 марта 2024
, 12 март→Основные результаты
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>. Вышеописанный процесс повторяется на протяжении нескольких шагов. На каждом шаге размер остаточного экземпляра уменьшается не менее чем в два раза, а количество контейнеров, необходимых для упаковки I0, увеличивается на аддитивную величину c. После log(Size(I0)) (?rf log(OPT(I))) шагов остаточный экземпляр имеет размер O(1) и может быть упакован в O(1) дополнительных контейнеров. □ | ||
