A sublinear-time approximation scheme for bin packing

The bin packing problem is defined as follows: given a set of n items with sizes 0 < w(1), w(2), .... w(n) <= 1, find a packing of these items into a minimum number Of Unit-size bins possible. We present a sublinear-time asymptotic approximation scheme for the bin packing problem; that is, for any epsilon > 0, we present an algorithm A, that has sampling access to the input instance and outputs a value k such that C-opt <= k <= (1 + epsilon) . C-opt + 1, where C-opt is the cost of an optimal solution. It is clear that uniform sampling by itself will not allow a sublinear-time algorithm in this setting; a small number of items might constitute most of the total weight and uniform samples will not hit them. In this work we use weighted samples, where item i is sampled with probability proportional to its weight: that is, with probability w(i)/Sigma w(i). In the presence of weighted samples, the approximation algorithm runs in (O) over tilde root n . poly(1/epsilon)) +g(1/x) time, where g(x) is an exponential function of x. When both weighted sampling and uniform sampling are allowed, (O) over tilde (n(1/3).poly(1/epsilon)) + g(1/epsilon) time suffices. In addition to an approximate value to Copt, our algorithm can also output a constant-size "template" of a packing that can later be used to find a near-optimal packing in linear time. (C) 2009 Elsevier B.V. All rights reserved.