On the Sum-of-Squares Algorithm for Bin Packing

Simple item page
dc.creatorCsirik, Janos
dc.creatorJohnson, David S.
dc.creatorKenyon, Claire
dc.creatorOrlin, James B.
dc.creatorShor, Peter W.
dc.creatorWeber, Richard R.
dc.date2002-10-14
dc.date2002-10-14
dc.date.accessioned2026-07-07T03:18:56Z
dc.date.available2026-07-07T03:18:56Z
dc.descriptionIn 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}.
dc.description72 pages
dc.identifierhttps://arxiv.org/abs/cs/0210013
dc.identifierhttp://arxiv.org/abs/cs/0210013
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31315
dc.subjectData Structures and Algorithms
dc.subjectF.2.2 G.3
dc.titleOn the Sum-of-Squares Algorithm for Bin Packing
dc.typetext

Files

Collections

arXiv