Алгоритмы упаковки бинов Кармаркара – Карпа

Кармаркара -Карпа ( KK ) Алгоритмы упаковки контейнеров представляют собой несколько связанных аппроксимационных алгоритмов для задачи упаковки контейнеров . Задача упаковки контейнеров — это задача упаковки предметов разного размера в контейнеры одинаковой вместимости так, чтобы общее количество контейнеров было как можно меньшим. Найти оптимальное решение вычислительно сложно . Кармаркар и Карп разработали алгоритм, который работает за полиномиальное время и находит решение не более чем за $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(OPT))$ бункеров, где OPT — количество бункеров в оптимальном решении. Они также разработали несколько других алгоритмов с немного другими гарантиями аппроксимации и ограничениями времени выполнения.

Алгоритмы КК считались прорывом в изучении упаковки бинов: известные ранее алгоритмы находили мультипликативную аппроксимацию, где число бинов не превышало $r\cdot \mathrm {OPT} +s$ для некоторых констант $r>1,s>0$, или самое большее $(1+\varepsilon )\mathrm {OPT} +1$. Алгоритмы КК были первыми, кто достиг аддитивной аппроксимации.

Вход

Исходными данными для задачи упаковки мусора является набор предметов разного размера a ₁ ,... a _n . Используются следующие обозначения:

• n - количество предметов.
• м – количество предметов разного размера. Для каждого i в 1,..., m :
  • s _i – i -й размер;
  • n _i — количество элементов размера s _i .
• B – размер бункера.

Учитывая экземпляр I , мы обозначаем:

• оптимальное решение экземпляра I. OPT(I) =
• FOPT( I ) = ( a ₁ +...+ a _n )/ B = теоретически оптимальное количество ячеек, когда все ячейки полностью заполнены предметами или фракциями предметов.

Очевидно, FOPT( I ) ≤ OPT(I).

Схема высокого уровня

Алгоритмы КК по существу решают конфигурационную линейную программу :

${\text{minimize}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{s.t.}}~~A\mathbf {x} \geq \mathbf {n} ~~~{\text{and}}~~\mathbf {x} \geq 0~~~{\text{and}}~~\mathbf {x} ~{\text{is an integer}}~$.

Здесь A — матрица из m строк. Каждый столбец A представляет возможную конфигурацию — мультимножество размеров элементов, такое, что сумма всех этих размеров не превышает B . Набор конфигураций C. — x — вектор размера C. Каждый элемент x _c из x представляет количество раз, когда конфигурация c используется .

• Пример : предположим, что размеры элементов равны 3,3,3,3,3,4,4,4,4,4 и B =12. Тогда существует C =10 возможных конфигураций: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. Матрица A имеет две строки: [4,3,2,2,1,1,1,0,0,0] для s=3 и [0,0,0,1,0, 1,2,1,2,3] для s=4. Вектор n равен [5,5], поскольку имеется по 5 элементов каждого размера. Возможным оптимальным решением является x =[1,0,0,0,0,0,1,0,0,1], что соответствует использованию трех бункеров с конфигурациями 3333, 344, 444.

В решении этой проблемы есть две основные трудности. Во-первых, это целочисленная линейная программа , которую сложно решить вычислительно. Во-вторых, количество переменных равно C — количеству конфигураций, которое может быть огромным. Алгоритмы КК справляются с этими трудностями, используя несколько методов, некоторые из которых уже были предложены Де-ла-Вегой и Люкером. Вот высокоуровневое описание алгоритма (где $I$ это исходный экземпляр):

• 1-а. Позволять $J$ быть экземпляром, созданным из $I$ удаляя мелкие предметы.
  • 2-а. Позволять $K$ быть экземпляром, созданным из $J$ путем группировки элементов и округления размера элементов в каждой группе до максимального значения в группе.
    • 3-а. Постройте конфигурационную линейную программу для $K$, без ограничений целочисленности.
      • 4. Вычислите (дробное) решение x для расслабленной линейной программы.
    • 3-б. Округляем x до интегрального решения для $K$.
  • 2-б. «Разгруппируйте» элементы, чтобы получить решение для $J$.
• 1-б. Добавьте мелкие предметы, чтобы получить решение $I$.

Ниже мы по очереди опишем каждый из этих шагов.

Шаг 1. Удаление и добавление мелких предметов

Мотивация удаления мелких предметов заключается в том, что, когда все предметы большие, количество предметов в каждой корзине должно быть небольшим, поэтому количество возможных конфигураций (относительно) невелико. Мы выбираем некоторую константу $g\in (0,1)$и удалить из исходного экземпляра $I$ все предметы меньше $g\cdot B$. Позволять $J$ быть результирующим экземпляром. Обратите внимание, что в $J$, каждый контейнер может содержать не более $1/g$ предметы. Мы упаковываем $J$ и получить упаковку с некоторыми $b_{J}$ контейнеры.

Теперь добавляем мелкие предметы в существующие корзины в произвольном порядке, пока есть место. Когда в существующих контейнерах больше нет места, мы открываем новый контейнер (как при упаковке следующего контейнера ). Позволять $b_{I}$ — количество контейнеров в окончательной упаковке. Затем:

$b_{I}\leq \max(b_{J},(1+2g)\cdot OPT(I)+1)$.

Доказательство . Если новые ячейки не открываются, то количество ячеек остается $b_{J}$. Если открывается новый контейнер, то все контейнеры, за исключением, возможно, последнего, содержат общий размер не менее $B-g\cdot B$, поэтому общий размер экземпляра не менее $(1-g)\cdot B\cdot (b_{I}-1)$. Поэтому, $FOPT\geq (1-g)\cdot (b_{I}-1)$, поэтому оптимальное решение требует как минимум $(1-g)\cdot (b_{I}-1)$ контейнеры. Так $b_{I}\leq OPT/(1-g)+1=(1+g+g^{2}+\ldots )OPT+1\leq (1+2g)OPT+1$. В частности, взяв g =1/ n , получим:

$b_{I}\leq \max(b_{J},OPT+2\cdot OPT(I)/n+1)\leq \max(b_{J},OPT+3)$,

с $OPT(I)\leq n$. Поэтому принято предполагать, что все элементы больше 1/ n .

Шаг 2. Группировка и разгруппировка элементов

Мотивацией группировки элементов является уменьшение количества элементов разных размеров, уменьшение количества ограничений в конфигурации LP. Общий процесс группировки таков:

• Упорядочивайте товары по убыванию размера.
• Разделите предметы на группы.
• Для каждой группы измените размер всех элементов в группе до максимального размера в группе.

Существует несколько различных методов группировки.

Линейная группировка

Позволять $k>1$ быть целочисленным параметром. Поставь самый большой $k$ предметы группы 1; следующий по величине $k$ предметы группы 2; и так далее (в последней группе может быть меньше $k$ предметы). Позволять $J$ быть исходным экземпляром. Позволять $K'$ быть первой группой (группой $k$ самые большие предметы) и $K$ сгруппированный экземпляр без первой группы. Затем:

• В $K'$ все предметы имеют одинаковый размер. В $K$ количество разных размеров $m(K)\leq n/k+1$.
• $OPT(K)\leq OPT(J)$ - с 1 группы в $J$ доминирует во 2 группе $K$ (все k предметов в группе 1 больше, чем k предметов в группе 2); аналогично, группа 2 в $J$ доминирует в группе 3 в $K$, и т. д.
• $OPT(K')\leq k$ - так как есть возможность упаковать каждый предмет в $K'$ в одну корзину.

Поэтому, $OPT(J)\leq OPT(K\cup K')\leq OPT(K)+OPT(K')\leq OPT(K)+k$. Действительно, при наличии решения $K$ с $b_{K}$ контейнеры, мы можем найти решение $J$ с максимум $b_{K}+k$ контейнеры.

Геометрическая группировка

Позволять $k>1$ быть целочисленным параметром. Геометрическая группировка происходит в два этапа:

• Разделить экземпляр $J$ в несколько экземпляров $J_{0},J_{1},\ldots$ такой, что в каждом случае $J_{r}$, все размеры находятся в интервале $[B/2^{r+1},B/2^{r})$. Обратите внимание: если все элементы в $J$ иметь размер хотя бы $g\cdot B$, то число экземпляров не более $\log _{2}(1/g)$.
• В каждом экземпляре $J_{r}$, выполнить линейное округление с параметром $k\cdot 2^{r}$. Позволять $K_{r},K'_{r}$ быть результирующими экземплярами. Позволять $K:=\cup _{r}K_{r}$ и $K':=\cup _{r}K'_{r}$.

Тогда количество различных размеров ограничено следующим образом:

• Для всех р , $m(K'_{r})=1$ и $m(K_{r})\leq n(J_{r})/(k\cdot 2^{r})+1$. Поскольку все предметы в $J_{r}$ больше, чем $B/2^{r+1}$, у нас есть $n(J_{r})\leq 2^{r+1}\cdot FOPT(J_{r})$, так $m(K_{r})\leq 2FOPT(J_{r})/k+1$. Суммирование по всем r дает $m(K)\leq 2FOPT(J)/k+\log _{2}(1/g)$.

Количество бункеров ограничено следующим образом:

• Для всех р , $OPT(K'_{r})\leq k$ - с $K'_{r}$ имеет $k\cdot 2^{r}$ предметы, и все они меньше, чем $B/2^{r}$, поэтому их можно упаковать не более чем в $k$ контейнеры.
• Поэтому, $OPT(K')\leq k\cdot \log _{2}(1/g)$.
• Поэтому, $OPT(J)\leq OPT(K)+OPT(K')\leq OPT(K)+k\cdot \log _{2}(1/g)$.

Альтернативная геометрическая группировка

Позволять $k>1$ быть целочисленным параметром. Упорядочивайте товары по убыванию размера. Разбейте их на группы так, чтобы общий размер каждой группы был не менее $k\cdot B$. Поскольку размер каждого элемента меньше B , количество элементов в каждой группе не менее $k+1$. Количество предметов в каждой группе слабо возрастает. Если все элементы больше $g\cdot B$, то количество предметов в каждой группе не более $k/g$. В каждой группе округляются только более крупные элементы. Это можно сделать так, чтобы:

• $m(K)\leq FOPT(J)/k+\ln(1/g)$.
• $OPT(J)\leq OPT(K)+2k\cdot (2+\ln(1/g))$.

Шаг 3. Построение ЛП и округление решения

Рассмотрим конфигурационную линейную программу без ограничений целочисленности:

${\text{minimize}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{s.t.}}~~A\mathbf {x} \geq \mathbf {n} ~~~{\text{and}}~~\mathbf {x} \geq 0$.

Здесь нам разрешено использовать дробное число каждой конфигурации.

• Пример : предположим, что имеется 31 элемент размера 3 и 7 элементов размера 4, а размер ячейки равен 10. Конфигурации: 4, 44, 34, 334, 3, 33, 333. Ограничения: [0,0 ,1,2,1,2,3]* x =31 и [1,2,1,1,0,0,0]* x =7. Оптимальным решением дробного LP является [0,0,0,7,0,0,17/3]. То есть: имеется 7 бункеров конфигурации 334 и 17/3 бункеров конфигурации 333. Обратите внимание, что только две разные конфигурации необходимы.

Обозначим оптимальное решение линейной программы через LOPT. Следующие отношения очевидны:

• FOPT(I) ≤ LOPT(I), поскольку FOPT(I) — это (возможно, дробное) количество ячеек, когда все ячейки полностью заполнены предметами или частями предметов. Очевидно, что ни одно решение не может быть более эффективным.
• LOPT(I) ≤ OPT(I), поскольку LOPT(I) — решение задачи минимизации с меньшим количеством ограничений.
• OPT(I) < 2*FOPT(I), поскольку в любой упаковке с минимум 2*FOPT(I) контейнерами сумма двух наименее полных контейнеров не превышает B , поэтому их можно объединить в один контейнер. .

Решение дробной ЛП можно округлить до целого решения следующим образом.

Предположим, у нас есть решение x дробной ЛП. Округляем x до решения интегральной ILP следующим образом.

• Пусть x — оптимальное базовое допустимое решение дробной ЛП. Предположим, это как $\sum _{c\in C}x_{c}=b_{L}$ контейнеры (обратите внимание, что $b_{L}$ может быть дробным числом). Поскольку дробный ЛП имеет m ограничений (по одному для каждого отдельного размера), x имеет не более m ненулевых переменных, то есть не более m используется различных конфигураций. Построим по x целостную упаковку, состоящую из главной и остаточной частей .
• Основная часть содержит напольные ( ) _для контейнеры каждой конфигурации c, которой xc _xc > 0.
• Для остаточной части (обозначенной R ) построим две упаковки-кандидата:
  • Один бункер каждой конфигурации c, для которого x _c > 0; всего m контейнеров. нужно
  • Жадная упаковка с количеством ячеек менее 2*FOPT( R ) (так как при наличии хотя бы 2 ячеек *FOPT( R ) два самых маленьких можно объединить).
• Для наименьшей из этих упаковок требуется min( m , 2*FOPT( R )) ≤ среднее ( m , 2*FOPT( R )) = FOPT(R) + m /2.
• Прибавив к этому округленные ячейки основной части, получим не более $b_{L}+m/2$ контейнеры.
• Время выполнения этого алгоритма преобразования составляет O( n log n ).

Это также подразумевает, что $OPT(I)\leq LOPT(I)+m/2$.

Шаг 4. Решение дробной ЛП

Основная проблема при решении дробной ЛП состоит в том, что она может иметь огромное количество переменных – по переменной для каждой возможной конфигурации.

Двойной LP

Двойная линейная программа дробного ЛП представляет собой:

${\text{maximize}}~~\mathbf {n} \cdot \mathbf {y} ~~~{\text{s.t.}}~~A^{T}\mathbf {y} \leq \mathbf {1} ~~~{\text{and}}~~\mathbf {y} \geq 0$.

Он имеет m переменных $y_{1},\ldots ,y_{m}$и ограничения C — ограничение для каждой конфигурации. Оно имеет следующую экономическую интерпретацию. Для каждого размера s мы должны определить неотрицательную цену. $y_{i}$. Наша прибыль — это общая стоимость всех товаров. Мы хотим максимизировать прибыль n y при условии, что общая цена товаров в каждой конфигурации не превышает 1. Теперь эта ЛП имеет только m переменных, но огромное количество ограничений. Даже перечислить все ограничения невозможно.

К счастью, можно решить задачу с любой заданной точностью, не перечисляя всех ограничений, используя вариант метода эллипсоида . Этот вариант получает в качестве входных данных оракул разделения : функцию, которая для вектора y ≥ 0 возвращает один из следующих двух вариантов:

• Утвердите, что y выполнимо, т.е. $A^{T}\mathbf {y} \leq \mathbf {1}$; или -
• Утвердите, что y недопустимо, и верните конкретное ограничение, которое нарушено, то есть вектор a такой, что $\mathbf {a} \cdot \mathbf {y} >1$.

Метод эллипсоида начинается с большого эллипсоида, который содержит всю допустимую область. $A^{T}\mathbf {y} \leq \mathbf {1}$. На каждом шаге t он занимает центр $\mathbf {y} _{t}$ текущего эллипсоида и отправляет его оракулу разделения:

• Если оракул говорит это $\mathbf {y} _{t}$ осуществима, то делаем «оптимальный разрез»: вырезаем из эллипсоида все точки y , для которых $\mathbf {n} \cdot \mathbf {y} <\mathbf {n} \cdot \mathbf {y} _{t}$. Эти точки определенно не являются оптимальными.
• Если оракул говорит это $\mathbf {y} _{t}$ недопустимо и нарушает ограничение a , то мы делаем «разрез осуществимости»: вырезаем из эллипсоида все точки y , для которых $\mathbf {a} \cdot \mathbf {y} >1$. Эти пункты определенно невыполнимы.

Сделав разрез, строим новый эллипсоид меньшего размера. Можно показать, что этот процесс сходится к приближенному решению, полиномиальному по времени требуемой точности.

Оракул разделения для двойного LP

Нам даны некоторые m неотрицательных чисел $y_{1},\ldots ,y_{m}$. Нам предстоит сделать выбор между следующими двумя вариантами:

• Для каждой допустимой конфигурации сумма $y_{i}$ соответствующее этой конфигурации не более 1; это означает, что y осуществимо.
• Существует допустимая конфигурация, для которой сумма $y_{i}$ больше 1; это означает, что y неосуществимо. В этом случае нам также придется вернуть конфигурацию.

Эту задачу можно решить, решив задачу о рюкзаке , где значения предметов равны $y_{1},\ldots ,y_{m}$, вес элемента равен $s_{1},\ldots ,s_{m}$, а грузоподъемность равна B (размер контейнера).

• Если общее значение оптимального ранцевого решения не превосходит 1, то мы говорим, что y осуществимо.
• Если общее значение оптимального ранцевого решения больше 1, то мы говорим, что y недопустимо, а элементы оптимального ранцевого решения соответствуют конфигурации, которая нарушает ограничение (поскольку $\mathbf {a} \cdot \mathbf {y} >1$ для вектора a, соответствующего этой конфигурации).

Задачу о рюкзаке можно решить с помощью динамического программирования за псевдополиномиальное время: $O(m\cdot V)$, где m — количество входов, а V — количество различных возможных значений. Чтобы получить алгоритм с полиномиальным временем, мы можем приближенно решить задачу о рюкзаке, используя округление входных данных. Предположим, нам нужно решение с толерантностью. $\delta$. Мы можем округлить каждый из $y_{1},\ldots ,y_{m}$ до ближайшего кратного $\delta$/ н . Тогда количество возможных значений от 0 до 1 равно n / $\delta$, а время выполнения $O(mn/\delta )$. Решение — это как минимум оптимальное решение минус $\delta$/ н .

Эллипсоидный метод с приближенным оракулом разделения

Метод эллипсоида следует адаптировать для использования приблизительного оракула разделения. Учитывая текущий центр эллипсоида $\mathbf {y} _{t}$:

• Если приблизительный оракул возвращает решение со значением больше 1, то $\mathbf {y} _{t}$ определенно неосуществимо, и решение соответствует конфигурации, которая нарушает ограничение a . Мы проводим «обработку технико-экономического обоснования» в $\mathbf {y} _{t}$, разрезая эллипсоид все точки y, для которых $\mathbf {a} \cdot \mathbf {y} >1$.
• Если приблизительный оракул возвращает решение со значением не более 1, то $\mathbf {y} _{t}$ может быть осуществимо, а может и нет, но $\mathbf {y} _{t}$ округлено в меньшую сторону (обозначим его через $\mathbf {z} _{t}$) возможно. По определению округления мы знаем, что $\mathbf {n} \cdot \mathbf {z} _{t}\geq \mathbf {n} \cdot \mathbf {y} _{t}-\mathbf {n} \cdot \mathbf {1} \cdot (\delta /n)=\mathbf {n} \cdot \mathbf {y} _{t}-\delta$. Мы все еще делаем «оптимальный разрез» в $\mathbf {y} _{t}$: вырезаем из эллипсоида все точки y, для которых $\mathbf {n} \cdot \mathbf {y} <\mathbf {n} \cdot \mathbf {y} _{t}$. Обратите внимание, что $\mathbf {y} _{t}$ может быть невозможным, поэтому его значение может быть больше, чем OPT. Поэтому мы могли бы удалить некоторые точки, цель которых оптимальна. Однако удаленные точки удовлетворяют $\mathbf {n} \cdot \mathbf {y} <\mathbf {n} \cdot \mathbf {z} _{t}+\delta \leq {\text{OPT}}+\delta$; ни одна точка не удаляется, если ее значение превышает значение в $\mathbf {z} _{t}$более чем $\delta$.

Использование оракула приближенного разделения дает допустимое решение y* двойственной ЛП с $\mathbf {n} \cdot \mathbf {y^{*}} \geq LOPT-\delta$, максимум через $Q$ итерации, где $Q=4m^{2}\ln(mn/g\delta )$. Общее время работы метода эллипсоида с приблизительным оракулом разделения равно $O(Qmn/\delta )$.

Устранение ограничений

В методе эллипсоида мы используем не более Q ограничений вида $\mathbf {a} \cdot \mathbf {y} \leq 1$. Все остальные ограничения можно устранить, поскольку они не влияют на результат y* метода эллипсоидов. Мы можем устранить еще больше ограничений. Известно, что в любой ЛП с m переменными существует набор из m ограничений, достаточный для определения оптимального решения (т. е. оптимальное значение одно и то же, даже если только эти m используются ограничений). Мы можем повторно запускать метод эллипсоида, как указано выше, каждый раз пытаясь удалить определенный набор ограничений. Если результирующая ошибка не превышает $\delta$, то мы навсегда удалим эти ограничения. Можно показать, что нам нужно не более $\approx (Q/m)+m\ln(Q/m)$ исключений, поэтому накапливаемая ошибка не превышает $\approx \delta \cdot [(Q/m)+m\ln(Q/m)]$. Если мы попробуем наборы ограничений детерминированно, то в худшем случае одно из m испытаний окажется успешным, поэтому нам нужно запустить не более чем метод эллипсоида. $\approx m\cdot [(Q/m)+m\ln(Q/m)]=Q+m^{2}\ln(Q/m)$ раз. Если мы выберем ограничения для удаления случайным образом, то ожидаемое количество итераций будет равно $O(m)\cdot [1+\ln(Q/m)]$.

Наконец, мы имеем сокращенную двойственную ЛП, содержащую только m переменных и m ограничений. Оптимальное значение приведенного ЛП составляет не менее $LOPT-h$, где $h\approx \delta \cdot [(Q/m)+m\ln(Q/m)]$.

Решение первичной ЛП

По теореме двойственности ЛП минимальное значение первичного ЛП равно максимальному значению двойственного ЛП, которое мы обозначили LOPT. Получив уменьшенную двойственную ЛП, мы берем ее двойственную и берем уменьшенную первичную ЛП. Этот LP имеет только m переменных, что соответствует только m из C. конфигураций Максимальное значение приведенного двойного ЛП составляет не менее $LOPT-h$. Это можно показать что оптимальное решение приведенной первичной ЛП не более $LOPT+h$. Решение обеспечивает почти оптимальную упаковку контейнеров с использованием не более m конфигураций.

Общее время выполнения детерминированного алгоритма, когда все элементы превышают $g\cdot B$, является:

$O\left({\frac {Qmn}{\delta }}\cdot (Q+m^{2}\ln {\frac {Q}{m}})\right)=O\left({\frac {Q^{2}mn+Qm^{3}n\ln {\frac {Q}{m}}}{\delta }}\right)\approx O\left(m^{8}\ln {m}\ln ^{2}({\frac {mn}{gh}})+{\frac {m^{4}n\ln {m}}{h}}\ln({\frac {mn}{gh}})\right)$,

Ожидаемое общее время работы рандомизированного алгоритма составляет: $O\left(m^{7}\log {m}\log ^{2}({\frac {mn}{gh}})+{\frac {m^{4}n\log {m}}{h}}\log({\frac {mn}{gh}})\right)$.

Сквозные алгоритмы

Кармаркар и Карп представили три алгоритма, которые используют описанные выше методы с разными параметрами. Время выполнения всех этих алгоритмов зависит от функции $T(\cdot ,\cdot )$, которая представляет собой полиномиальную функцию, описывающую время, необходимое для решения дробной задачи ЛП с допуском h = 1, то есть для детерминированной версии: $T(m,n)\in O(m^{8}\log {m}\log ^{2}{n}+m^{4}n\log {m}\log {n})$.

Алгоритм 1

Позволять $\epsilon >0$ быть константой, представляющей желаемую точность аппроксимации.

• 1-а. Набор $g=\max(1/n,\epsilon /2)$. Позволять $J$ быть экземпляром, созданным из $I$ удалив все элементы размером меньше g .
  • 2-а. Набор $k=n\cdot \epsilon ^{2}$. Позволять $K$ быть экземпляром, созданным из $J$ линейной группировкой с параметром k и пусть $K'$ быть оставшимся экземпляром (группой из k крупнейших элементов). Обратите внимание, что $m(K)\leq n/k+1\approx 1/\epsilon ^{2}$.
    • 3-а. Постройте конфигурационную линейную программу для $K$, без ограничений целочисленности.
      • 4. Вычислите решение x для $K$, с допуском h =1. В результате получается дробная упаковка контейнеров с $b_{L}\leq LOPT(K)+1$ контейнеры. Время выполнения $T(m(K),n(K))\leq T(\epsilon ^{-2},n)$.
    • 3-б. Округляем x до интегрального решения для $K$. Добавить максимум $m(K)/2$ бункеры для дробной части. Общее количество бункеров $b_{K}\leq b_{L}+m(K)/2\leq LOPT(K)+1+1/2\epsilon ^{2}$.
  • 2-б. Упакуйте вещи в $K'$ использование не более k ячеек; получить упаковку $J$. Количество бункеров $b_{J}\leq b_{K}+k\leq LOPT(K)+1+1/2\epsilon ^{2}+n\cdot \epsilon ^{2}$.
• 1-б. Сложите элементы меньше g, чтобы получить решение задачи $I$. Количество бункеров: $b_{I}\leq \max(b_{J},(1+2g)\cdot OPT(I)+1)\leq (1+\epsilon )OPT(I)+1/2\epsilon ^{2}+3$.

В общем, количество бункеров указано в $(1+\epsilon )OPT+O(\epsilon ^{-2})$ и время выполнения находится в $O(n\log n+T(\epsilon ^{-2},n))$. Выбрав $\epsilon =OPT^{-1/3}$ мы получаем $OPT+O(OPT^{2/3})$.

Алгоритм 2

Позволять $g>0$ быть действительным параметром и $k>0$ целочисленный параметр, который будет определен позже.

• 1-а. Позволять $J$ быть экземпляром, созданным из $I$ удалив все элементы размером меньше g .
• 2. Пока $FOPT(J)>1+{\frac {k}{k-1}}\ln(1/g)$ делать:
  • 2-а. Выполните альтернативную геометрическую группировку с параметром k . Позволять $K$ будет результирующим экземпляром, и пусть $K'$ быть оставшимся экземпляром. У нас есть $m(K)\leq FOPT(J)/k+\ln(1/g)$.
    • 3-а. Постройте конфигурационную линейную программу для $K$, без ограничений целочисленности.
      • 4. Вычислите решение x для $K$, с допуском h =1. В результате получается дробная упаковка контейнеров с $b_{L}\leq LOPT(K)+1$ контейнеры. Время выполнения $T(m(K),n(K))\leq T(FOPT(J)/k+\ln(1/g),n)$.
    • 3-б. Округляем x до интегрального решения для $K$. Не добавляйте интервалы для дробной части. Вместо этого просто извлеките упакованные предметы из $J$.
  • 2-б. Упакуйте вещи в $K'$ максимум в $2k\cdot (2+\ln(1/g))$ контейнеры.
• 2. Один раз $FOPT(J)\leq 1+{\frac {k}{k-1}}\ln(1/g)$, жадно упакуйте оставшиеся предметы максимум в $2FOPT(J)\leq 2+{\frac {2k}{k-1}}\ln(1/g)$ контейнеры.
  • На каждой итерации цикла на шаге 2 дробная часть x имеет не более m ( K ) шаблонов, поэтому $FOPT(J_{t+1})\leq m(K_{t})\leq FOPT(J_{t})/k+\ln(1/g)$. FOPT уменьшается в k раз на каждой итерации, поэтому количество итераций не превышает ${\frac {\ln FOPT(I)}{\ln k}}+1$.
  • Таким образом, общее количество бункеров, используемых для $J$ является: $b_{J}\leq OPT(I)+\left[1+{\frac {\ln FOPT(I)}{\ln k}}\right]\left[1+4k+2k\ln(1/g)\right]+2+{\frac {2k}{k-1}}\ln(1/g)$.
• 1-б. Сложите элементы меньше g, чтобы получить решение задачи $I$. Количество бункеров: $b_{I}\leq \max(b_{J},(1+2g)\cdot OPT(I)+1)$.

Время выполнения находится в $O(n\log n+T(FOPT(J)/k+\ln(1/g),n))$.

Теперь, если мы выберем k =2 и g =1/FOPT(I), мы получим:

$b_{J}\leq OPT+O(\log ^{2}(FOPT))$,

и следовательно:

$b_{I}\leq \max(b_{J},OPT+2OPT/FOPT+1)\leq \max(b_{J},OPT+5)\in OPT+\log ^{2}(OPT)$,

поэтому общее количество ячеек находится в $OPT+O(\log ^{2}(FOPT))$. Время выполнения $O(n\log n)+T(FOPT/2+\ln(FOPT),n)\in O(n\log {n}+T(FOPT,n))$.

Один и тот же алгоритм можно использовать с разными параметрами для достижения компромисса между временем выполнения и точностью. По какому-то параметру $\alpha \in (0,1)$, выбирать $k=FOPT^{\alpha }$ и $g=1/FOPT^{1-\alpha }$. Тогда упаковка требует максимум $\mathrm {OPT} +{\mathcal {O}}(OPT^{\alpha })$ bins, а время выполнения находится в $O(n\log {n}+T(FOPT^{(1-\alpha )},n))$.

Алгоритм 3

Третий алгоритм полезен, когда количество размеров m невелико (см. также упаковку контейнеров с высокой кратностью ).

• 1-а. Набор $g={\frac {\log ^{2}(m)}{FOPT(I)}}$. Позволять $K$ быть экземпляром, созданным из $I$ удалив все элементы размером меньше g .
• Если $m(K)\leq FOPT(K)$ затем:
  • 3-а. Постройте конфигурационную линейную программу для $K$, без ограничений целочисленности.
    • 4. Вычислите решение x для $K$, с допуском h =1. В результате получается дробная упаковка контейнеров с $b_{L}\leq LOPT(K)+1$ контейнеры. Время выполнения $T(m(K),n(K))\leq T(\epsilon ^{-2},n)$.
  • 3-б. Округляем x до интегрального решения для $K$. Не добавляйте интервалы для дробной части. Вместо этого просто извлеките упакованные предметы из $K$.
• Запустите шаг 2 алгоритма 2 на оставшихся частях.
• 1-б. Сложите элементы меньше g, чтобы получить решение задачи $I$. Количество бункеров: $b_{I}\leq \max(b_{J},(1+2g)\cdot OPT(I)+1)$.

Он использует максимум $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}m)$ bins, а время выполнения находится в $O(n\log {n}+T(m,n))$.

Улучшения

Позднее методы КК были усовершенствованы, чтобы обеспечить еще лучшее приближение.

Ротвосс использует ту же схему, что и алгоритм 2, но с другой процедурой округления на этапе 2. Он ввел этап «склеивания», на котором мелкие элементы склеиваются вместе, чтобы получить один более крупный элемент. С помощью этой склейки можно увеличить размер самого маленького предмета примерно до $B/\log ^{12}(n)$. Когда все размеры не менее $B/\log ^{12}(n)$, мы можем заменить $g=1/\log ^{12}(n)$ в гарантии Алгоритма 2 и получим:

$b_{J}\leq OPT(I)+O(\log(FOPT)\log(\log(n)))$,

что дает $\mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ контейнеры.

Хоберг и Ротвосс используйте аналогичную схему, при которой предметы сначала упаковываются в «контейнеры», а затем контейнеры упаковываются в контейнеры. Их алгоритм требует максимум $b_{J}\leq OPT(I)+O(\log(OPT))$ контейнеры.