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

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




Здесь aS,i – количество предметов размера si в допустимом множестве S. Обозначим за q(I) количество различных размеров в наборе I. Число нетривиальных ограничений в LP равно q(I), что означает, что существует базовое оптимальное решение этой линейной программы, в котором только q(I) переменных заданы нецелочисленными. Кармаркар и Карп используют это наблюдение весьма нетрививальным способом. Следующая лемма описывает их основную идею.
Здесь <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 предположим, что существует алгоритмическая процедура округления для получения другого экземпляра J0, такого, что в J0 имеется Size(J)/2 различных размеров элементов, и J и J0 связаны в следующем смысле: любая дробно-линейная упаковка J с использованием I контейнеров позволяет получить дробно-линейную упаковку J0 с не более чем I контейнерами, а любая упаковка J0 с использованием I' контейнеров позволяет получить упаковку J с использованием I' + c контейнеров, где c – некоторый фиксированный параметр. Затем J может быть упакована с использованием OPT(J) + c ■ log(OPT(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) дополнительных контейнеров. □




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