High-multiplicity bin packing

Suppose first that all items are large, that is, every s_i is at least e·B for some fraction e>0. Then, the total number of items in each bin is at most 1/e, so the total number of configuration is at most d^1/e. Each configuration appears at most n times. Therefore, there are at most ${\displaystyle n^{d^{1/e}}}$ combinations to check. For each combination, we have to check d constraints (one for each size), so the run-time is ${\displaystyle d\cdot n^{d^{1/e}}}$, which is polynomial in n when d, e are constant.[1]

The main problem with this algorithm (besides the fact that it works only when the items are large) is that its runtime is polynomial in n, but the length of the input (in binary representation) is linear in log(V), which is of the order of magnitude of log(n).

Filippi and Agnetis[2] presented an algorithm that finds a solution with at most OPT+d-2 bins in time O(poly(log V)). In particular, for d=2 different sizes, their algorithm finds an optimal solution in time O(log V).

Goemans and Rothvoss[3][4] presented an algorithm for any fixed d, that finds the optimal solution when all numbers are given in binary encoding. Their algorithm solves the following problem: given two d-dimensional polytopes P and Q, find the minimum number of integer points in P whose sum lies in Q. Their algorithm runs in time ${\displaystyle (\log V)^{2^{O(d)}}}$. Their algorithm can be adapted to other problems, such as Identical-machines scheduling and unrelated-machines scheduling with various constraints.

Lueker and de-la-Vega and [5] invented the idea of adaptive input rounding. Order the items by their size, and group them into 1/e² groups of cardinality ne². In each group, round the sizes upwards to the maximum size in the group. Now, there are only d=1/e² different sizes. The solution of the rounded instance is feasible for the original instance too, but the number of bins may be larger than necessary. To quantify the loss, consider the instance rounded down to the maximum size in the previous group (the first group is rounded down to 0). The rounded-down instance D is almost equal to the rounded-up instance U, except that in D there are some ne² zeros while in U there are some ne² large items instead; but their size is at most B. Therefore, U requires at most ne² more bins than D. Since D requires fewer bins than the optimum, we get that Bins(U) ≤ OPT + ne², that is, we have an additive error that can be made as small as we like by choosing e.

If all items are large (of size at least eB), then each bin in OPT contains at most 1/e items (of size at least eB), so OPT must be at least en. Therefore, Bins(U) ≤ (1+e)OPT. After handling the small items, we get at most ${\displaystyle (1+2e)\mathrm {OPT} +1}$.

Karmarkar and Karp[6] present a more efficient rounding method which they call geometric rounding (in contrast to the linear rounding of de-la-Vega and Lueker). Based on these innovations, they present an algorithm with run-time polynomial in ${\displaystyle n}$ and ${\displaystyle 1/\varepsilon }$. Their algorithm finds a solution with size at most ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))}$.

This technique was later improved by several authors:

• Rothvoss[7] presented an algorithm that generates a solution with size at most ${\displaystyle \mathrm {OPT} +O(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))}$.

• Hoberg and Rothvoss[8] improved this algorithm to generate a solution with size at most ${\displaystyle \mathrm {OPT} +O(\log(\mathrm {OPT} ))}$. The algorithm is randomized, and its running-time is polynomial in the total number of items.