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

Здесь <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 предположим, что существует алгоритмическая процедура округления для получения другого экземпляра 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)) контейнеров.

Остается описать процедуру округления. Рассмотрим элементы в неубывающем порядке <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) и заполняя их только в конце (подобно алгоритму де ла Веги и Люкера).

'''Следствие 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> – константа.