Access Restriction

Author Csirik, Janos ♦ Johnson, David S. ♦ Kenyon, Claire ♦ Orlin, James B. ♦ Shor, Peter W. ♦ Weber, Richard R.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2006
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Approximation algorithms ♦ Average case analysis ♦ Bin packing
Abstract In this article we present a theoretical analysis of the online $\textit{Sum-of-Squares}$ algorithm $(\textit{SS})$ for bin packing along with several new variants. $\textit{SS}$ is applicable to any instance of bin packing in which the bin capacity $\textit{B}$ and item sizes $\textit{s}(\textit{a})$ are integral (or can be scaled to be so), and runs in time $\textit{O}(\textit{nB}).$ It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, $\textit{SS}$ also has sublinear expected waste. For any discrete distribution where the optimal expected waste is bounded, $\textit{SS}$ has expected waste at most $\textit{O}(log$ $\textit{n}).$ We also discuss several interesting variants on $\textit{SS},$ including a randomized $\textit{O}(\textit{nB}$ log $\textit{B})-time$ online algorithm $\textit{SS}*$ whose expected behavior is essentially optimal for all discrete distributions. Algorithm $\textit{SS}*$ depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution $\textit{F},$ just what is the growth rate for the optimal expected waste.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2006-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 53
Issue Number 1
Page Count 65
Starting Page 1
Ending Page 65

Open content in new tab

   Open content in new tab
Source: ACM Digital Library