An Efficient Approximation Scheme for Variable-Sized Bin Packing

In the classical bin packing problem one is required to pack a given list of items into the smallest possible number of unit-sized bins. Because this problem is NP-complete, researchers have tried to find efficient approximation algorithms that solve this problem in a reasonable amount of time. If we let $A(I)$ be the number of bins used by algorithm A to pack a list of items I, and OPT(I) be the minimum number of bins necessary to pack I, one defines the asymptotic performance ratio of A to be A(I) / OPT(I), as OPT(I) tends to infinity. De la Vega and Lueker presented an approximation scheme, which for any ∈ > 0, yields an approximation algorithm with performance ratio 1 + ε. This scheme has time complexity polynomial in n, the number of items, but exponential in 1 / ε. Karmarkar and Karp extended this scheme to one that has time complexity polynomial in n and 1 / ε. In the variable-sized bin packing problem, one is given a list of items to pack and a set of different bin sizes to be used in packing the items. For an algorithm A, $A(I)$ is the sum of the sizes of the bins used to pack the list I. This sum is the quantity one wishes to minimize. Friesen and Langston presented an approximation algorithm with performance ratio 4/3 with time complexity polynomial in the number of items and the number of different bin sizes. In this paper we present an approximation scheme which for any given positive a produces a scheme with performance ratio 1 + ε. This algorithm has time complexity polynomial in the number of items, the number of bins, and 1 / ε.