Проблема с крышкой мусорного бака

В задаче о покрытии контейнеров предметы разных размеров должны быть упакованы в конечное число контейнеров или контейнеров, каждый из которых должен содержать по крайней мере определенный заданный общий размер таким образом, чтобы максимально увеличить количество используемых контейнеров.

Эта задача является двойственной задаче об упаковке контейнеров : при покрытии контейнеров размеры контейнеров ограничены снизу, и цель состоит в том, чтобы максимизировать их количество; при упаковке контейнеров размеры контейнеров ограничены сверху , и цель состоит в том, чтобы минимизировать их количество.

Задача NP-сложная , но существуют различные эффективные алгоритмы аппроксимации :

• Алгоритмы, охватывающие как минимум 1/2, 2/3 или 3/4 оптимального количества интервалов асимптотически, работают во времени. $O(n),O(n\log n),O(n{\log }^{2}n)$ соответственно.
• Асимптотический PTAS , алгоритмы с ограниченным поведением в худшем случае, ожидаемое поведение которых является асимптотически оптимальным для некоторых дискретных распределений, и алгоритм обучения с асимптотически оптимальным ожидаемым поведением для всех дискретных распределений.
• Асимптотический FPTAS .

Алгоритм двунаправленного заполнения контейнеров

Csirik, Frenk, Lebbe and Zhang представьте следующий простой алгоритм для аппроксимации 2/3. Предположим, что размер ячейки равен 1 и в ней n предметов.

• Расположите предметы от самого большого (1) до самого маленького ( n ).
• Заполните корзину самыми большими предметами : 1, 2, ..., m , где m — наибольшее целое число, для которого сумма предметов 1, ..., m меньше 1.
• Добавляйте в эту корзину самые маленькие предметы : n , n -1, ..., пока его значение не превысит 1.

Для любого случая I обозначим через $\mathrm {OPT} (I)$ количество интервалов в оптимальном решении и $\mathrm {BDF} (I)$ количество полных бункеров в алгоритме двунаправленного заполнения. Затем $\mathrm {BDF} (I)\geq (2/3)\mathrm {OPT} (I)-(2/3)$или, что то же самое, $\mathrm {OPT} (I)\leq (3/2)\mathrm {BDF} (I)+1$.

Доказательство

Для доказательства используется следующая терминология.

• $t:=\mathrm {BDF} (I)=$ количество ячеек, заполняемых алгоритмом.
• $B_{1},\ldots ,B_{t}:=$ ячеек t , заполненных алгоритмом.
• Начальные элементы — t элементов, которые первыми вставляются в каждую из t ячеек.
• Последние элементы — t элементов, которые вставляются последними в каждую из t ячеек.
• Средние предметы – все предметы, которые не являются ни начальными, ни конечными.
• $w$ := количество конечных элементов, которые не превышают 1/2 (эквивалентно, $t-w$ — количество конечных элементов больше 1/2).

Сумма каждого бункера $B_{1},\ldots ,B_{t}$ не меньше 1, но если из него убрать последний элемент, то оставшаяся сумма будет меньше 1. Каждый из первых $w$ контейнеры $B_{1},\ldots ,B_{w}$ содержит начальный элемент, возможно, несколько промежуточных элементов и последний элемент. Каждый из последних $t-w$ контейнеры $B_{w+1},\ldots ,B_{t}$ содержит только начальный элемент и конечный элемент, поскольку оба они больше 1/2 и их сумма уже больше 1.

Доказательство рассматривает два случая.

Самый простой случай $w=t$, то есть все конечные элементы меньше 1/2. Тогда сумма всех заполненных $B_{i}$ не превышает 3/2, а сумма остальных элементов не превышает 1, поэтому сумма всех элементов не превосходит $3t/2+1$. С другой стороны, в оптимальном решении сумма каждого контейнера равна не менее 1, поэтому сумма всех элементов не менее $\mathrm {OPT} (I)$. Поэтому, $\mathrm {OPT} (I)\leq 3t/2+1$ по мере необходимости.

Тяжелый случай – это $w<t$, то есть некоторые конечные элементы больше 1/2. Теперь мы докажем верхнюю оценку $\mathrm {OPT} (I)$ представив его в виде суммы $\mathrm {OPT} (I)=|K_{0}|+|K_{1}|+|K_{2}|$ где:

• $K_{0}:=$ оптимальные ячейки без начальных/конечных предметов (только средние предметы).
• $K_{1}:=$ оптимальные ячейки ровно с одним начальным/конечным предметом (и некоторыми промежуточными предметами).
• $K_{2}:=$ оптимальные ячейки с двумя или более начальными/конечными предметами (и некоторыми промежуточными предметами).

Сначала мы сосредоточимся на оптимальных бункерах в $K_{0}$ и $K_{1}$. Мы представляем биекцию между элементами в каждом таком контейнере и некоторыми элементами в $B_{1},\ldots ,B_{t}$ которые, по крайней мере, не менее ценны.

• Единственный начальный/конечный элемент в $K_{1}$ bins сопоставляется с исходным элементом в $B_{1},\ldots ,B_{|K_{1}|}$. Обратите внимание, что это самые крупные начальные элементы.
• Средние предметы в $K_{0}$ и $K_{1}$ бункеры сопоставляются со средними элементами в $B_{1},\ldots ,B_{w}$. Обратите внимание, что эти корзины содержат все средние предметы.
• Поэтому все предметы в $K_{0}$ и $K_{1}$ сопоставляются со всеми неконечными элементами в $B_{1},\ldots ,B_{|K_{1}|}$, плюс все средние элементы в $B_{|K_{1}|+1},\ldots ,B_{w}$.
• Сумма каждого бункера $B_{1},\ldots ,B_{w}$ без его конечного элемента меньше 1. Более того, начальный элемент больше 1/2, поэтому сумма только средних элементов меньше 1/2. Следовательно, сумма всех неконечных элементов в $B_{1},\ldots ,B_{|K_{1}|}$, плюс все средние элементы в $B_{|K_{1}|+1},\ldots ,B_{w}$, не более $|K_{1}|+(w-|K_{1}|)/2=(|K_{1}|+w)/2$.
• Сумма каждого оптимального интервала не менее 1. Следовательно: $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$, что подразумевает $2|K_{0}|+|K_{1}|\leq w\leq t$.

Теперь мы сосредоточимся на оптимальных контейнерах в $K_{1}$ и $K_{2}$.

• Общее количество начальных/конечных элементов в $K_{1}$ и $K_{2}$ контейнеры - это как минимум $|K_{1}|+2|K_{2}|$, но их общее число также $2t$ поскольку в каждой корзине ровно два начальных/конечных товара. Поэтому, $|K_{1}|+2|K_{2}|\leq 2t$.
• Суммируя последние два неравенства, следует, что $2\mathrm {OPT} (I)\leq 3t$, что подразумевает $\mathrm {OPT} (I)\leq 3t/2$.

Герметичность

Коэффициент 2/3 является жестким для BDF. Рассмотрим следующий пример (где $\epsilon >0$ достаточно мал): $${\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 6k~{\text{units}}\cdots \}~&~\{\cdots 6k~{\text{units}}\cdots \}\end{aligned}}$$BDF инициализирует первую корзину самым большим товаром и заполняет ее $6k$ самые маленькие предметы. Затем оставшиеся $6k$ предметы могут покрывать контейнеры только тройками, так что в целом $2k+1$ контейнеры заполнены. Но в ОПТ можно заполнить $3k$ корзины, каждая из которых содержит два предмета среднего размера и два мелких предмета.

Алгоритм заполнения трех классов контейнеров

Csirik, Frenk, Lebbe and Zhang представить другой алгоритм, который достигает приближения 3/4. Алгоритм упорядочивает элементы от большего к меньшему и разделяет их на три класса:

• X: Предметы размером не менее 1/2;
• Y: предметы размером менее 1/2 и не менее 1/3;
• Z: Предметы размером менее 1/3.

Алгоритм работает в два этапа. Этап 1:

• Инициализируйте новую корзину либо с самым большим предметом в X, либо с двумя самыми большими предметами в Y, в зависимости от того, что больше. Обратите внимание, что в обоих случаях начальная сумма интервала меньше 1.
• Заполните новую корзину предметами из Z в порядке возрастания стоимости.
• Повторяйте до тех пор, пока XUY или Z не станут пустыми.

Этап 2:

• Если XUY пуст, заполните ячейки элементами из Z по простому правилу следующего соответствия.
• Если Z пуст, упакуйте предметы, оставшиеся в X, попарно, а оставшиеся в Y — по тройкам.

В приведенном выше примере, показывающем герметичность BDF, наборы: $${\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\\{|X|=1\}~&~\{\cdots |Y|=6k\cdots \}~&~\{\cdots |Z|=6k\cdots \}\end{aligned}}$$TCF достигает оптимального результата, поскольку инициализирует все $3k$ корзины с парами предметов из Y и заполняют их парами предметов из Z.

Для любого случая I обозначим через $\mathrm {OPT} (I)$ количество интервалов в оптимальном решении и $\mathrm {TCF} (I)$ количество полных бункеров в алгоритме заполнения трех классов. Затем $\mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)$.

Коэффициент 3/4 является жестким для TCF. Рассмотрим следующий пример (где $\epsilon >0$ достаточно мал):

$${\begin{aligned}{\tfrac {1}{2}}-6k\epsilon ,{\tfrac {1}{2}}-6k\epsilon ,~&~{\tfrac {1}{3}}-\epsilon ,\ldots ,{\tfrac {1}{3}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 12k~{\text{units}}\cdots \}~&~\{\cdots 12k~{\text{units}}\cdots \}\end{aligned}}$$

TCF инициализирует первый контейнер двумя самыми большими элементами и заполняет его $12k$ самые маленькие предметы. Затем оставшиеся $12k$ предметы могут покрывать контейнеры только группами по четыре, так что в целом $3k+1$ контейнеры заполнены. Но в ОПТ можно заполнить $4k$ корзины, в каждой из которых находится по 3 предмета среднего размера и 3 предмета мелкого размера.

Схемы аппроксимации с полиномиальным временем

Чирик, Джонсон и Кеньон представить асимптотическую PTAS. Это алгоритм, который для каждого ε > 0 заполняет не менее $(1-5\varepsilon )\cdot \mathrm {OPT} (I)-4$ корзины, если сумма всех предметов больше $13B/\epsilon ^{3}$, и по крайней мере $(1-2\varepsilon )\cdot \mathrm {OPT} (I)-1$ в противном случае. Он работает во времени $O(n^{1/\varepsilon ^{2}})$. Алгоритм решает вариант конфигурации линейной программы , с $n^{1/\varepsilon ^{2}}$переменные и $1+1/\varepsilon ^{2}$ ограничения. Этот алгоритм интересен только теоретически, поскольку для того, чтобы получить приближение лучше, чем 3/4, мы должны принять $\varepsilon <1/20$, и тогда число переменных больше, чем $n^{400}$.

Они также представляют алгоритмы для онлайн- версии проблемы. В онлайн-режиме невозможно получить асимптотический коэффициент аппроксимации для наихудшего случая лучше, чем 1/2. Однако существуют алгоритмы, которые хорошо работают в среднем случае.

Янсен и Солис-Оба представить асимптотическую FPTAS. Это алгоритм, который для каждого ε > 0 заполняет не менее $(1-\varepsilon )\cdot \mathrm {OPT} (I)-1$ корзины, если сумма всех предметов больше $13B/\epsilon ^{3}$ (если сумма предметов меньше этого значения, то оптимум не превышает $13/\epsilon ^{3}\in O(1/\epsilon ^{3})$ в любом случае). Он работает во времени $O\left({\frac {1}{\epsilon ^{5}}}\cdot \ln {\frac {n}{\varepsilon }}\cdot \max {(n^{2},{\frac {1}{\varepsilon }}\ln \ln {\frac {1}{\varepsilon ^{3}}})}+{\frac {1}{\varepsilon ^{4}}}{\mathcal {T_{M}}}({\frac {1}{\varepsilon ^{2}}})\right)$, где ${\mathcal {T_{M}}}(n)$ — это сложность выполнения наилучшего доступного алгоритма обращения матрицы (в настоящее время около $O(n^{2.38})$). Этот алгоритм становится лучше, чем приближение 3/4 уже тогда, когда $\varepsilon <1/4$, и в этом случае константы разумные - около $2^{10}n^{2}+2^{18}$.

Производительность с делимыми размерами предметов

Важным частным случаем покрытия ячеек является то, что размеры элементов образуют делимую последовательность (также называемую факторизованной ). Особый случай делящихся размеров элементов возникает при распределении памяти в компьютерных системах, где все размеры элементов представляют собой степени 2. Если размеры элементов делятся, то некоторые эвристические алгоритмы покрытия ячеек находят оптимальное решение.

Связанные проблемы

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

Реализации

• Python: пакет prtpy содержит реализацию алгоритмов Чирика-Френка-Лаббе-Чжана .