Loading...
Please wait, while we are loading the content...
Similar Documents
On the Sum-of-Squares Algorithm for Bin Packing
| Content Provider | arXiv |
|---|---|
| Author | Csirik, Janos Johnson, David S. Kenyon, Claire Orlin, James B. Shor, Peter W. Weber, Richard R. |
| Date of Submission | 2002-10-14 |
| Abstract | 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}. |
| Related Links | https://arxiv.org/pdf/cs/0210013.pdf |
| Page Count | 72 |
| arXiv | cs/0210013 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Data Structures and Algorithms Computer Science |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
