Computer Science – Data Structures and Algorithms
Scientific paper
2002-10-14
Computer Science
Data Structures and Algorithms
72 pages
Scientific paper
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}.
Csirik Janos
Johnson David S.
Kenyon Claire
Orlin James B.
Shor Peter W.
No associations
LandOfFree
On the Sum-of-Squares Algorithm for Bin Packing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Sum-of-Squares Algorithm for Bin Packing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Sum-of-Squares Algorithm for Bin Packing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-412057