On the Sum-of-Squares algorithm for bin packing

DOI10.1145/1120582.1120583zbMATH Open1326.68334DBLPjournals/jacm/CsirikJKOSW06arXivcs/0210013OpenAlexW1992365301WikidataQ56813486 ScholiaQ56813486MaRDI QIDQ3546292FDOQ3546292

D. S. Johnson, Claire Kenyon, Richard Weber, Peter W. Shor, János Csirik, James B. Orlin

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

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(logn)$. In addition, we discuss several interesting variants on $SS$, including a randomized $O(nBlogB)$-time on-line algorithm $S{S}^{*}$, based on $SS$, whose expected behavior is essentially optimal for all discrete distributions. Algorithm $S{S}^{*}$ 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}.

Full work available at URL: https://arxiv.org/abs/cs/0210013

zbMATH Keywords

approximation algorithmsbin packingaverage case analysis

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Cited In (10)

• A Service System with Packing Constraints: Greedy Randomized Algorithm Achieving Sublinear in Scale Optimality Gap
• Algorithm NextFit for the bin packing problem
• Adaptive Bin Packing with Overflow
• Sum-of-squares heuristics for bin packing and memory allocation
• Approximation and online algorithms for multidimensional bin packing: a survey
• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• Exact and approximate methods for a one-dimensional minimax bin-packing problem
• On a generalized bin-packing problem
• Interior-Point-Based Online Stochastic Bin Packing
• Large-scale heterogeneous service systems with general packing constraints

This page was built for publication: On the Sum-of-Squares algorithm for bin packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546292)