Bin covering problem

In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used.

This problem is a dual of the bin packing problem: in bin covering, the bin sizes are bounded from below and the goal is to maximize their number; in bin packing, the bin sizes are bounded from above and the goal is to minimize their number. ^[1]

The problem is NP-hard, but there are various efficient approximation algorithms:

• Algorithms covering at least 1/2, 2/3 or 3/4 of the optimum bin count asymptotically, running in time ${\displaystyle O(n),O(n\log n),O(n{\log }^{2}n)}$ respectively. ^{[1] [2]}
• An asymptotic PTAS, algorithms with bounded worst-case behavior whose expected behavior is asymptotically-optimal for some discrete distributions, and a learning algorithm with asymptotically optimal expected behavior for all discrete distributions. ^[3]
• An asymptotic FPTAS. ^[4]

The bidirectional bin-filling algorithm

Csirik, Frenk, Lebbe and Zhang ^{[2] : 16–19} present the following simple algorithm for 2/3 approximation. Suppose the bin size is 1 and there are n items.

• Order the items from the largest (1) to smallest (n).
• Fill a bin with the largest items: 1, 2, ..., m, where m is the largest integer for which the sum of items 1, ..., m is less than 1.
• Add to this bin the smallest items: n, n-1, ..., until its value raises above 1.

For any instance I, denote by ${\displaystyle \mathrm {OPT} (I)}$ the number of bins in the optimal solution, and by ${\displaystyle \mathrm {BDF} (I)}$ the number of full bins in the bidirectional filling algorithm. Then ${\displaystyle \mathrm {BDF} (I)\geq (2/3)\mathrm {OPT} (I)-(2/3)}$, or equivalently, ${\displaystyle \mathrm {OPT} (I)\leq (3/2)\mathrm {BDF} (I)+1}$.

Proof

For the proof, the following terminology is used.

• ${\displaystyle t:=\mathrm {BDF} (I)=}$ the number of bins filled by the algorithm.
• ${\displaystyle B_{1},\ldots ,B_{t}:=}$ the t bins filled by the algorithm.
• Initial items - the t items that are inserted first into each of the t bins.
• Final items - the t items that are inserted last into each of the t bins.
• Middle items - all items that are neither initial nor final.
• ${\displaystyle w}$ := the number of final items that are at most 1/2 (equivalently, ${\displaystyle t-w}$ is the number of final items larger than 1/2).

The sum of each bin ${\displaystyle B_{1},\ldots ,B_{t}}$ is at least 1, but if the final item is removed from it, then the remaining sum is smaller than 1. Each of the first ${\displaystyle w}$ bins ${\displaystyle B_{1},\ldots ,B_{w}}$ contains an initial item, possibly some middle items, and a final item. Each of the last ${\displaystyle t-w}$ bins ${\displaystyle B_{w+1},\ldots ,B_{t}}$ contains only an initial item and a final item, since both of them are larger than 1/2 and their sum is already larger than 1.

The proof considers two cases.

The easy case is ${\displaystyle w=t}$, that is, all final items are smaller than 1/2. Then, the sum of every filled ${\displaystyle B_{i}}$ is at most 3/2, and the sum of remaining items is at most 1, so the sum of all items is at most ${\displaystyle 3t/2+1}$. On the other hand, in the optimal solution the sum of every bin is at least 1, so the sum of all items is at least ${\displaystyle \mathrm {OPT} (I)}$. Therefore, ${\displaystyle \mathrm {OPT} (I)\leq 3t/2+1}$ as required.

The hard case is ${\displaystyle w<t}$, that is, some final items are larger than 1/2. We now prove an upper bound on ${\displaystyle \mathrm {OPT} (I)}$ by presenting it as a sum ${\displaystyle \mathrm {OPT} (I)=|K_{0}|+|K_{1}|+|K_{2}|}$ where:

• ${\displaystyle K_{0}:=}$ the optimal bins with no initial/final items (only middle items).
• ${\displaystyle K_{1}:=}$ the optimal bins with exactly one initial/final item (and some middle items).
• ${\displaystyle K_{2}:=}$ the optimal bins with two or more initial/final items (and some middle items).

We focus first on the optimal bins in ${\displaystyle K_{0}}$ and ${\displaystyle K_{1}}$. We present a bijection between the items in each such bin to some items in ${\displaystyle B_{1},\ldots ,B_{t}}$ which are at least as valuable.

• The single initial/final item in the ${\displaystyle K_{1}}$ bins is mapped to the initial item in ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$. Note that these are the largest initial items.
• The middle items in the ${\displaystyle K_{0}}$ and ${\displaystyle K_{1}}$ bins are mapped to the middle items in ${\displaystyle B_{1},\ldots ,B_{w}}$. Note that these bins contain all the middle items.
• Therefore, all items in ${\displaystyle K_{0}}$ and ${\displaystyle K_{1}}$ are mapped to all non-final items in ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$, plus all middle items in ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}}$.
• The sum of each bin ${\displaystyle B_{1},\ldots ,B_{w}}$ without its final item is less than 1. Moreover, the initial item is more than 1/2, so the sum of only the middle items is less than 1/2. Therefore, the sum of all non-final items in ${\displaystyle B_{1},\ldots ,B_{|K_{1}|}}$, plus all middle items in ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}}$, is at most ${\displaystyle |K_{1}|+(w-|K_{1}|)/2=(|K_{1}|+w)/2}$.
• The sum of each optimal bin is at least 1. Hence: ${\displaystyle |K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2}$, which implies ${\displaystyle 2|K_{0}|+|K_{1}|\leq w\leq t}$.

We now focus on the optimal bins in ${\displaystyle K_{1}}$ and ${\displaystyle K_{2}}$.

• The total number of initial/final items in the ${\displaystyle K_{1}}$ and ${\displaystyle K_{2}}$ bins is at least ${\displaystyle |K_{1}|+2|K_{2}|}$, but their total number is also ${\displaystyle 2t}$ since there are exactly two initial/final items in each bin. Therefore, ${\displaystyle |K_{1}|+2|K_{2}|\leq 2t}$.
• Summing the latter two inequalities implies that ${\displaystyle 2\mathrm {OPT} (I)\leq 3t}$, which implies ${\displaystyle \mathrm {OPT} (I)\leq 3t/2}$.

Tightness

The 2/3 factor is tight for BDF. Consider the following instance (where ${\displaystyle \epsilon >0}$ is sufficiently small):$${\displaystyle {\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 initializes the first bin with the largest item and fills it with the ${\displaystyle 6k}$ smallest items. Then, the remaining ${\displaystyle 6k}$ items can cover bins only in triplets, so all in all ${\displaystyle 2k+1}$ bins are filled. But in OPT one can fill ${\displaystyle 3k}$ bins, each of which contains two of the middle-sized items and two small items.

Three-classes bin-filling algorithm

Csirik, Frenk, Lebbe and Zhang ^{[2] : 19–24} present another algorithm that attains a 3/4 approximation. The algorithm orders the items from large to small, and partitions them into three classes:

• X: The items with size at least 1/2;
• Y: The items with size less than 1/2 and at least 1/3;
• Z: The items with size less than 1/3.

The algorithm works in two phases. Phase 1:

• Initialize a new bin with either the largest item in X, or the two largest items in Y, whichever is larger. Note that in both cases, the initial bin sum is less than 1.
• Fill the new bin with items from Z in increasing order of value.
• Repeat until either X U Y or Z are empty.

Phase 2:

• If X U Y is empty, fill bins with items from Z by the simple next-fit rule.
• If Z is empty, pack the items remaining in X by pairs, and those remaining in Y by triplets.

In the above example, showing the tightness of BDF, the sets are:$${\displaystyle {\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 attains the optimal outcome, since it initializes all ${\displaystyle 3k}$ bins with pairs of items from Y, and fills them with pairs of items from Z.

For any instance I, denote by ${\displaystyle \mathrm {OPT} (I)}$ the number of bins in the optimal solution, and by ${\displaystyle \mathrm {TCF} (I)}$ the number of full bins in the three-classes filling algorithm. Then ${\displaystyle \mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I)-4)}$.

The 3/4 factor is tight for TCF. Consider the following instance (where ${\displaystyle \epsilon >0}$ is sufficiently small):

$${\displaystyle {\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 initializes the first bin with the largest two items, and fills it with the ${\displaystyle 12k}$ smallest items. Then, the remaining ${\displaystyle 12k}$ items can cover bins only in groups of four, so all in all ${\displaystyle 3k+1}$ bins are filled. But in OPT one can fill ${\displaystyle 4k}$ bins, each of which contains 3 middle-sized items and 3 small items.

Polynomial-time approximation schemes

Csirik, Johnson and Kenyon ^[3] present an asymptotic PTAS. It is an algorithm that, for every ε>0, fills at least ${\displaystyle (1-5\varepsilon )\cdot \mathrm {OPT} (I)-4}$ bins if the sum of all items is more than ${\displaystyle 13B/\epsilon ^{3}}$, and at least ${\displaystyle (1-2\varepsilon )\cdot \mathrm {OPT} (I)-1}$ otherwise. It runs in time ${\displaystyle O(n^{1/\varepsilon ^{2}})}$. The algorithm solves a variant of the configuration linear program, with ${\displaystyle n^{1/\varepsilon ^{2}}}$variables and ${\displaystyle 1+1/\varepsilon ^{2}}$ constraints. This algorithm is only theoretically interesting, since in order to get better than 3/4 approximation, we must take ${\displaystyle \varepsilon <1/20}$, and then the number of variables is more than ${\displaystyle n^{400}}$.

They also present algorithms for the online version of the problem. In the online setting, it is not possible to get an asymptotic worst-case approximation factor better than 1/2. However, there are algorithms that perform well in the average case.

Jansen and Solis-Oba ^[4] present an asymptotic FPTAS. It is an algorithm that, for every ε>0, fills at least ${\displaystyle (1-\varepsilon )\cdot \mathrm {OPT} (I)-1}$ bins if the sum of all items is more than ${\displaystyle 13B/\epsilon ^{3}}$ (if the sum of items is less than that, then the optimum is at most ${\displaystyle 13/\epsilon ^{3}\in O(1/\epsilon ^{3})}$ anyway). It runs in time ${\displaystyle 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)}$, where ${\displaystyle {\mathcal {T_{M}}}(n)}$ is the runtime complexity of the best available algorithm for matrix inversion (currently, around ${\displaystyle O(n^{2.38})}$). This algorithm becomes better than the 3/4 approximation already when ${\displaystyle \varepsilon <1/4}$, and in this case the constants are reasonable - about ${\displaystyle 2^{10}n^{2}+2^{18}}$.

Performance with divisible item sizes

An important special case of bin covering is that the item sizes form a divisible sequence (also called factored). A special case of divisible item sizes occurs in memory allocation in computer systems, where the item sizes are all powers of 2. If the item sizes are divisible, then some of the heuristic algorithms for bin covering find an optimal solution. ^{[5] : Sec.5}

Related problems

In the fair item allocation problem, there are different people each of whom attributes a different value to each item. The goal is to allocate to each person a "bin" full of items, such that the value of each bin is at least a certain constant, and as many people as possible receive a bin. Many techniques from bin covering are used in this problem too.

Implementations

• Python: The prtpy package contains an implementation of the Csirik-Frenk-Labbe-Zhang algorithms.

References

1. Assmann, S. F.; Johnson, D. S; Kleitman, D. J; Leung, J. Y. -T (1984-12-01). "On a dual version of the one-dimensional bin packing problem". Journal of Algorithms. 5 (4): 502–525. doi:10.1016/0196-6774(84)90004-X. ISSN   0196-6774.
2. Csirik, János; J. B. G. Frenk and M. Labbé and S. Zhang (1999-01-01). "Two simple algorithms for bin covering". Acta Cybernetica. 14 (1): 13–25. ISSN   2676-993X.
3. Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). "Better approximation algorithms for bin covering". Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '01. Washington, D.C., USA: Society for Industrial and Applied Mathematics: 557–566. ISBN   978-0-89871-490-6.
4. Jansen, Klaus; Solis-Oba, Roberto (2003). "An asymptotic fully polynomial time approximation scheme for bin covering". Theoretical Computer Science . 306 (1–3): 543–551. doi:10.1016/S0304-3975(03)00363-3. MR   2000192.
5. Coffman, E. G; Garey, M. R; Johnson, D. S (1987-12-01). "Bin packing with divisible item sizes". Journal of Complexity. 3 (4): 406–428. doi:10.1016/0885-064X(87)90009-4. ISSN   0885-064X.