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.
A configuration is a set of items that can fit into a single bin.
It can be represented by a vector of d integers, denoting the multiplicities of the different sizes in the configuration.
The total number of bins used is simply the sum of xc over all configurations, denoted by 1·x.
The total number of items used from each size is the sum of the vectors ac · xc over all configurations c. Then, the problem is to minimize 1·x such that the sum of ac · xc, over all configurations c, is at least n, so that all items are packed.
Suppose first that all items are large, that is, every si is at least e·B for some fraction e>0.
For each combination, we have to check d constraints (one for each size), so the run-time is
[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.
Lueker and de-la-Vega and [5] invented the idea of adaptive input rounding.
Therefore, U requires at most ne2 more bins than D. Since D requires fewer bins than the optimum, we get that Bins(U) ≤ OPT + ne2, 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.
Based on these innovations, they present an algorithm with run-time polynomial in