  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}.
