### On the Sum-of-Squares algorithm for bin packingOn the Sum-of-Squares algorithm for bin packing

Access Restriction
Subscribed

 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

Source: ACM Digital Library