4431
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 44: | Строка 44: | ||
Здесь | Здесь <math>a_{S,i}</math> – количество предметов размера <math>s_i</math> в допустимом множестве S. Обозначим за <math>q(I)</math> количество различных размеров в наборе <math>I</math>. Число нетривиальных ограничений в LP равно <math>q(I)</math>, что означает, что существует базовое оптимальное решение этой линейной программы, в котором только <math>q(I)</math> переменных заданы нецелочисленными. Кармаркар и Карп используют это наблюдение весьма нетривиальным способом. Следующая лемма описывает их основную идею. | ||
Лемма 3. Для любого заданного экземпляра J предположим, что существует алгоритмическая процедура округления для получения другого экземпляра | '''Лемма 3'''. Для любого заданного экземпляра J предположим, что существует алгоритмическая процедура округления для получения другого экземпляра J', такого, что в J' имеется Size(J)/2 различных размеров элементов, и J и J' связаны в следующем смысле: любая дробно-линейная упаковка J с использованием <math>\ell</math> контейнеров позволяет получить дробно-линейную упаковку J' с не более чем <math>\ell</math> контейнерами, а любая упаковка J' с использованием <math>\ell'</math> контейнеров позволяет получить упаковку J с использованием <math>\ell + c</math> контейнеров, где c – некоторый фиксированный параметр. Затем J может быть упакована с использованием OPT(J) + c <math>\cdot</math> log(OPT(J)) контейнеров. | ||
Доказательство. Пусть I0 = I и пусть I1 – экземпляр, полученный в результате применения процедуры округления к I0. Согласно свойству процедуры округления, OPT(I) < OPT(I1) + c и LP(I1) < LP(I). Поскольку в h имеется Size(I0)/2 различных размеров, решение LP для I1 имеет не более Size(I0)/2 дробно заданных переменных. Удалим элементы, упакованные в LP-решении цельным образом, и рассмотрим остаточный экземпляр I10. Заметим, что Size(I10) < Size(I0)/2. Теперь снова применим процедуру округления к I10, чтобы получить I2, и решим задачу LP для I2. И вновь это решение имеет не более Size(I10)/2 < Size(I0)/4 дробно заданных переменных, а OPT(I10) < OPT(I2) + c и LP(I2) < LP(I10). Вышеописанный процесс повторяется на протяжении нескольких шагов. На каждом шаге размер остаточного экземпляра уменьшается не менее чем в два раза, а количество контейнеров, необходимых для упаковки I0, увеличивается на аддитивную величину c. После log(Size(I0)) (?rf log(OPT(I))) шагов остаточный экземпляр имеет размер O(1) и может быть упакован в O(1) дополнительных контейнеров. □ | |||
'''Доказательство'''. Пусть I0 = I и пусть I1 – экземпляр, полученный в результате применения процедуры округления к I0. Согласно свойству процедуры округления, OPT(I) < OPT(I1) + c и LP(I1) < LP(I). Поскольку в h имеется Size(I0)/2 различных размеров, решение LP для I1 имеет не более Size(I0)/2 дробно заданных переменных. Удалим элементы, упакованные в LP-решении цельным образом, и рассмотрим остаточный экземпляр I10. Заметим, что Size(I10) < Size(I0)/2. Теперь снова применим процедуру округления к I10, чтобы получить I2, и решим задачу LP для I2. И вновь это решение имеет не более Size(I10)/2 < Size(I0)/4 дробно заданных переменных, а OPT(I10) < OPT(I2) + c и LP(I2) < LP(I10). Вышеописанный процесс повторяется на протяжении нескольких шагов. На каждом шаге размер остаточного экземпляра уменьшается не менее чем в два раза, а количество контейнеров, необходимых для упаковки I0, увеличивается на аддитивную величину c. После log(Size(I0)) (?rf log(OPT(I))) шагов остаточный экземпляр имеет размер O(1) и может быть упакован в O(1) дополнительных контейнеров. □ | |||
правка