Karmarkar–Karp bin packing algorithms

The Karmarkar-Karp (KK) 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.

The KK 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] The KK algorithms were the first ones to attain an additive approximation.

The KK 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

The main tool used by the KK algorithms is the fractional configuration linear program:

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

Here, A is a matrix with m rows. Each column of A represents a feasible configuration - a multiset of item-sizes, such that the sum of all these sizes is at most B. The set of configurations is C. x is a vector of size C. Each element x_c of x represents the number of times configuration c is used. If x is integral then the solution to this problem is exactly OPT. Since x is allowed to be fractional, the solution might be smaller; denote it by LOPT. Moreover, let FOPT = (a₁+...+a_n)/B = the theoretically-optimal number of bins, when all bins are completely filled with items or item fractions. The following relations are obvious:

• FOPT(I) ≤ LOPT(I), since FOPT(I) is the (possibly fractional) number of bins when all bins are completely filled with items or fractions of items. Clearly, no solution can be more efficient.
• LOPT(I) ≤ OPT(I), since LOPT(I) is a solution to a minimization problem with fewer constraints.
• OPT(I) < 2*FOPT(I), since in any packing with at least 2*FOPT(I) bins, the sum of the two least-full bins is at most B, so they can be combined into a single bin.

The dual LP

The dual linear program of the fractional LP is:

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

It has S variables y₁,...,y_S, and C constraints - one for each configuration. It has the following economic interpretation. For each size s, we should determine a nonnegative price y_s. Our profit is the total price of all items. We want to maximize the profit n y subject to the constraints that the total price of items in each configuration is at most 1.

Solving the fractional LP

A linear program with no integrality constraints can be solved in time polynomial in the number of variables and constraints. The problem is that the number of variables in the fractional configuration LP is equal to the number of possible configurations, which might be huge. Karmarkar and Karp present an algorithm that, for any tolerance factor h, finds a basic feasible solution of cost at most LOPT(I) + h, and runs in time:

${\displaystyle O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)}$ ,

where S is the number of different sizes, n is the number of different items, and the size of the smallest item is eB. In particular, if e ≥ 1/n and h=1, the algorithm finds a solution with at most LOPT+1 bins in time: ${\displaystyle O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)}$ .

A randomized variant of this algorithm runs in expected time:

${\displaystyle O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)}$ .

Their algorithm uses separation oracle to the dual LP.

Rounding the fractional LP

Given an optimal solution to the fractional LP, it can be rounded into a solution for the integral ILP, proving that OPT(I) ≤ LOPT(I) + m/2:

• Let x be an optimal basic feasible solution of the fractional LP. By definition, the value of x is LOPT(I). Since the fractional LP has S constraints, x has at most S nonzero variables, that is, at most S different configurations are used. We construct from x an integral packing consisting of a principal part and a residual part.
• The principal part contains floor(x_c) bins of each configuration c for which x_c > 0.
• For the residual part (denoted by R), we construct two candidate packings:
  • A single bin of each configuration c for which x_c > 0; all in all S bins are needed.
  • A greedy packing, with fewer than 2*FOPT(R) bins (since if there are at least 2*FOPT(R) bins, the two smallest ones can be combined).
• The smallest of these packings requires min(S, 2*FOPT(R)) ≤ average(S, 2*FOPT(R)) = FOPT(R) + S/2.
• Adding to this the rounded-down bins of the principal part yields LOPT(I) + S/2.
• The execution time of this conversion algorithm is O(n log n).

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