On the sum-of-squares algorithm for bin packing

J. Csirik, D.S. Johnson, C. Kenyon, J.B. Orlin, P.W. Shor and R.R. Weber. , in Proc. 32nd Annual ACM Symp. on Theory of Computing, 2001, to appear.

Abstract

In this paper we present a theoretical analysis of the deterministic
on-line Sum of Squares algorithm (SS) for bin packing, introduced and
studied experimentally in [8], along with several new variants. SS is
applicable to any instance of bin packing in which the bin capacity B
and item sizes s(a) are integral (or can be scaled to be so), and runs
in time O(nB). It performs remarkably well from an average case point
of view: For any discrete distribution in which the optimal expected
waste is sublinear, SS also has sub- linear expected waste. For any
discrete distribution where the optimal expected waste is bounded, SS
has expected waste at most O(log n). In addition, we present a ran-
domized O(nB log B)-time on-line algorithm SS* , based on SS, whose
expected behavior is essentially optimal for all discrete
distributions. Algorithm SS* also depends on a new
linear-programming-based pseudopolynomial-time algorithm for solving
the NP-hard problem of determining, given a discrete distribution F,
just what is the growth rate for the optimal expected waste. An
off-line randomized variant SS** performs well in a worst-case sense:
For any listL of integer-sized items to be packed into bins of a fixed
size B, the expected number of bins used by SS** is at most OPT(L) +
OPT(L).

back to list of papers