On the Sum-of-Squares Algorithm for Bin Packing
<|reference_start|>On the Sum-of-Squares Algorithm for Bin Packing: In this paper we present a theoretical analysis of the deterministic on-line {\em Sum of Squares} algorithm ($SS$) for bin packing introduced and studied experimentally in \cite{CJK99}, 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 sublinear 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 discuss several interesting variants on $SS$, including a randomized $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. This article is a greatly expanded version of the conference paper \cite{sumsq2000}.<|reference_end|>
@article{csirik2002on,
    title={On the Sum-of-Squares Algorithm for Bin Packing},
    author={Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter
  W. Shor, and Richard R. Weber},
    journal={arXiv preprint arXiv:cs/0210013},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0210013},
    primaryClass={cs.DS}
}