Bin covering problem

Last updated February 25, 2024

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.

Algorithms covering at least 1/2, 2/3 or 3/4 of the optimum bin count asymptotically, running in time $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 $\mathrm {OPT} (I)$ the number of bins in the optimal solution, and by $\mathrm {BDF} (I)$ the number of full bins in the bidirectional filling algorithm. Then $\mathrm {BDF} (I)\geq (2/3)\mathrm {OPT} (I)-(2/3)$ , or equivalently, $\mathrm {OPT} (I)\leq (3/2)\mathrm {BDF} (I)+1$ .

Proof

For the proof, the following terminology is used.

$t:=\mathrm {BDF} (I)=$ the number of bins filled by the algorithm.
$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.
$w$ := the number of final items that are at most 1/2 (equivalently, $t-w$ is the number of final items larger than 1/2).

The sum of each bin $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 $w$ bins $B_{1},\ldots ,B_{w}$ contains an initial item, possibly some middle items, and a final item. Each of the last $t-w$ bins $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 $w=t$ , that is, all final items are smaller than 1/2. Then, the sum of every filled $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 $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 $\mathrm {OPT} (I)$ . Therefore, $\mathrm {OPT} (I)\leq 3t/2+1$ as required.

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

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

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

The single initial/final item in the $K_{1}$ bins is mapped to the initial item in $B_{1},\ldots ,B_{|K_{1}|}$ . Note that these are the largest initial items.
The middle items in the $K_{0}$ and $K_{1}$ bins are mapped to the middle items in $B_{1},\ldots ,B_{w}$ . Note that these bins contain all the middle items.
Therefore, all items in $K_{0}$ and $K_{1}$ are mapped to all non-final items in $B_{1},\ldots ,B_{|K_{1}|}$ , plus all middle items in $B_{|K_{1}|+1},\ldots ,B_{w}$ .
The sum of each bin $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 $B_{1},\ldots ,B_{|K_{1}|}$ , plus all middle items in $B_{|K_{1}|+1},\ldots ,B_{w}$ , is at most $|K_{1}|+(w-|K_{1}|)/2=(|K_{1}|+w)/2$ .
The sum of each optimal bin is at least 1. Hence: $|K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2$ , which implies $2|K_{0}|+|K_{1}|\leq w\leq t$ .

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

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

Tightness

The 2/3 factor is tight for BDF. Consider the following instance (where $\epsilon >0$ is sufficiently small):

{\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 $6k$ smallest items. Then, the remaining $6k$ items can cover bins only in triplets, so all in all $2k+1$ bins are filled. But in OPT one can fill $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:

{\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 $3k$ bins with pairs of items from Y, and fills them with pairs of items from Z.

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

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

{\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 $12k$ smallest items. Then, the remaining $12k$ items can cover bins only in groups of four, so all in all $3k+1$ bins are filled. But in OPT one can fill $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 $(1-5\varepsilon )\cdot \mathrm {OPT} (I)-4$ bins if the sum of all items is more than $13B/\epsilon ^{3}$ , and at least $(1-2\varepsilon )\cdot \mathrm {OPT} (I)-1$ otherwise. It runs in time $O(n^{1/\varepsilon ^{2}})$ . The algorithm solves a variant of the configuration linear program, with $n^{1/\varepsilon ^{2}}$ variables and $1+1/\varepsilon ^{2}$ constraints. This algorithm is only theoretically interesting, since in order to get better than 3/4 approximation, we must take $\varepsilon <1/20$ , and then the number of variables is more than $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 $(1-\varepsilon )\cdot \mathrm {OPT} (I)-1$ bins if the sum of all items is more than $13B/\epsilon ^{3}$ (if the sum of items is less than that, then the optimum is at most $13/\epsilon ^{3}\in O(1/\epsilon ^{3})$ anyway). It runs in time $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 ${\mathcal {T_{M}}}(n)$ is the runtime complexity of the best available algorithm for matrix inversion (currently, around $O(n^{2.38})$ ). This algorithm becomes better than the 3/4 approximation already when $\varepsilon <1/4$ , and in this case the constants are reasonable - about $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

Implementations

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

Related Research Articles

The knapsack problem is the following problem in combinatorial optimization:

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset $of integers and a target-sum, and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete too, for example:$

In continuum mechanics, the infinitesimal strain theory is a mathematical approach to the description of the deformation of a solid body in which the displacements of the material particles are assumed to be much smaller than any relevant dimension of the body; so that its geometry and the constitutive properties of the material at each point of space can be assumed to be unchanged by the deformation.

In linear algebra, an $n$ -by- $n$ square matrix $A$ is called invertible if there exists an $n$ -by- $n$ square matrix $B$ such that

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, and technology mapping in FPGA semiconductor chip design.

In extremal graph theory, Szemerédi’s regularity lemma states that a graph can be partitioned into a bounded number of parts so that the edges between parts are regular. The lemma shows that properties of random graphs can be applied to general graphs like counting the copies of a given subgraph within graphs. Endre Szemerédi proved the lemma over bipartite graphs for his theorem on arithmetic progressions in 1975 and for general graphs in 1978. Variants of the lemma use different notions of regularity and apply to other mathematical objects like hypergraphs.

A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value which is at least $times the correct value, and at most times the correct value.$

Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.

In mathematics, the Grothendieck inequality states that there is a universal constant $with the following property. If M ij is an n \times n matrix with$

In statistics, an additive model (AM) is a nonparametric regression method. It was suggested by Jerome H. Friedman and Werner Stuetzle (1981) and is an essential part of the ACE algorithm. The AM uses a one-dimensional smoother to build a restricted class of nonparametric regression models. Because of this, it is less affected by the curse of dimensionality than e.g. a p-dimensional smoother. Furthermore, the AM is more flexible than a standard linear model, while being more interpretable than a general regression surface at the cost of approximation errors. Problems with AM, like many other machine-learning methods, include model selection, overfitting, and multicollinearity.

In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes, typically just one. These algorithms are designed to operate with limited memory, generally logarithmic in the size of the stream and/or in the maximum value in the stream, and may also have limited processing time per item.

In quantum field theory, a Ward–Takahashi identity is an identity between correlation functions that follows from the global or gauge symmetries of the theory, and which remains valid after renormalization.

The strip packing problem is a 2-dimensional geometric minimization problem. Given a set of axis-aligned rectangles and a strip of bounded width and infinite height, determine an overlapping-free packing of the rectangles into the strip, minimizing its height. This problem is a cutting and packing problem and is classified as an Open Dimension Problem according to Wäscher et al.

In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the identical-machines scheduling problem. The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers, whose sum is k*T.

Identical-machines scheduling is an optimization problem in computer science and operations research. We are given n jobs J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on m identical machines, such that a certain objective function is optimized, for example, the makespan is minimized.

Next-fit is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem. The next-fit algorithm uses the following heuristic:

First-fit (FF) is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem. The first-fit algorithm uses the following heuristic:

First-fit-decreasing (FFD) is an algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem, so we use an approximately-optimal heuristic.

High-multiplicity bin packing is a special case of the bin packing problem, in which the number of different item-sizes is small, while the number of items with each size is large. While the general bin-packing problem is NP-hard, the high-multiplicity setting can be solved in polynomial time, assuming that the number of different sizes is a fixed constant.

The Karmarkar–Karp (KK) bin packing algorithms are several related approximation algorithm for the bin packing problem. The bin packing problem is a problem of packing items of different sizes into bins of identical capacity, such that the total number of bins is as small as possible. Finding the optimal solution is computationally hard. Karmarkar and Karp devised an algorithm that runs in polynomial time and finds a solution with at most $bins, where OPT is the number of bins in the optimal solution. They also devised several other algorithms with slightly different approximation guarantees and run-time bounds.$

References

1 2 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.
1 2 3 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.
1 2 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.
1 2 Jansen, Klaus; Solis-Oba, Roberto (2002-11-21). "An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering". Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC '02. Berlin, Heidelberg: Springer-Verlag. 2518: 175–186. doi:10.1007/3-540-36136-7_16. ISBN 978-3-540-00142-3.
↑ 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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 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.

[:1-2] 1 2 3 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.

[:2-3] 1 2 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.

[:3-4] 1 2 Jansen, Klaus; Solis-Oba, Roberto (2002-11-21). "An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering". Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC '02. Berlin, Heidelberg: Springer-Verlag. 2518: 175–186. doi:10.1007/3-540-36136-7_16. ISBN 978-3-540-00142-3.

[:02-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.

[1]

[2]

[3]

[4]

[5]