Karmarkar–Karp bin packing algorithms

The Karmarkar-Karp bin packing algorithms are several related approximation algorithm for the bin packing problem.^[1] 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 ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}(OPT))}$ 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.

Their algorithms were considered a breakthrough in the study of bin packing: the previously-known algorithms found multiplicative approximation, where the number of bins was at most ${\displaystyle r\cdot \mathrm {OPT} +s}$ for some constants ${\displaystyle r>1,s>0}$, or at most ${\displaystyle (1+\varepsilon )\mathrm {OPT} +1}$.^[2] Their techniques were improved later, to provide even better approximations: an algorithm by Rothvoss^[3] uses at most ${\displaystyle \mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))}$bins, and an algorithm by Hoberg and Rothvoss^[4] uses at most ${\displaystyle \mathrm {OPT} +O(\log(\mathrm {OPT} ))}$ bins.

Input

The input to a bin-packing problem is a set of items of different sizes, a₁,...a_n. The following notation is used:

• n - the number of items.
• m - the number of different item sizes. For each i in 1,...,m:
  • s_i is the i-th size;
  • n_i is the number of items of size s_i.
• B - the bin size.
• e - a fraction in (0,1), such that eB is the smallest size of an item.

Guarantees

Karmarkar and Karp presented four different algorithms. The run-time of all these algorithms depends on a function ${\displaystyle T(\cdot ,\cdot )}$ , which is a polynomial function describing the time it takes to solve the configuration linear program: ${\displaystyle T(m,n)\in O(m^{8}\log {m}\log ^{2}{n}+m^{4}n\log {m}\log {n})}$ . The algorithms attain the following guarantees:

• At most ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}OPT)}$  bins, with run-time in ${\displaystyle O(T(FOPT,n))}$ .
• At most ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}m)}$  bins, with run-time in ${\displaystyle O(T(m,n))}$ .
• At most ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(OPT^{\alpha })}$  bins, with run-time in ${\displaystyle O(T(FOPT^{(1-\alpha )},n))}$ , where ${\displaystyle \alpha \in (0,1)}$  is a constant.
• At most ${\displaystyle (1+\epsilon )\mathrm {OPT} +{\mathcal {O}}(\epsilon ^{-2})}$  bins, with run-time in ${\displaystyle O(T(\epsilon ^{-2},n))}$ , where ${\displaystyle \epsilon >0}$  is a constant.

Fractional bin packing

• FOPT = (a₁+...+a_n)/B = the theoretically-optimal number of bins, when all bins are completely filled with items or item fractions.

References

1. Karmarkar, Narendra; Karp, Richard M. (November 1982). "An efficient approximation scheme for the one-dimensional bin-packing problem". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982): 312–320. doi:10.1109/SFCS.1982.61. S2CID 18583908.
2. Fernandez de la Vega, W.; Lueker, G. S. (1981). "Bin packing can be solved within 1 + ε in linear time". Combinatorica. 1 (4): 349–355. doi:10.1007/BF02579456. ISSN 1439-6912. S2CID 10519631.
3. Rothvoß, T. (2013-10-01). "Approximating Bin Packing within O(log OPT * Log Log OPT) Bins". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science: 20–29. arXiv:1301.4010. doi:10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7. S2CID 15905063.
4. Hoberg, Rebecca; Rothvoss, Thomas (2017-01-01), "A Logarithmic Additive Integrality Gap for Bin Packing", Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 2616–2625, doi:10.1137/1.9781611974782.172, ISBN 978-1-61197-478-2, S2CID 1647463, retrieved 2021-02-10