A sublinear-time approximation scheme for bin packing

The bin packing problem is defined as follows: given a set of n items with sizes 00, we present an algorithm Aϵ that has sampling access to the input instance and outputs a value k such that , where 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 wi/∑iwi. In the presence of weighted samples, the approximation algorithm runs in time, where g(x) is an exponential function of x. When both weighted sampling and uniform sampling are allowed, time suffices. In addition to an approximate value to , 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.