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 , 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