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 ϵ > 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 + ϵ ) ⋅ 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 / ∑ i w i. In the presence of weighted samples, the approximation algorithm runs in O ̃ ( n ⋅ poly ( 1 / ϵ ) ) + g ( 1 / ϵ ) time, where g ( x ) is an exponential function of x. When both weighted sampling and uniform sampling are allowed, O ̃ ( n 1 / 3 ⋅ poly ( 1 / ϵ ) ) + g ( 1 / ϵ ) time suffices. In addition to an approximate value to C opt, 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.

Authors

• Tuğkan Batu
• Petra Berenbrink
• Christian Sohler

Keywords

• Sublinear-time algorithms
• Bin packing