On the Sum-of-Squares algorithm for bin packing

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

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

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}^{\ast }$, based on $SS$, whose expected behavior is essentially optimal for all discrete distributions. Algorithm $S{S}^{\ast }$ 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

Recommendations

• On the sum-of-squares algorithm for bin packing
• Sum-of-squares heuristics for bin packing and memory allocation
• An O(n) bin-packing algorithm for uniformly distributed data
• Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings
• scientific article; zbMATH DE number 1870507

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 (12)

• On the sum-of-squares algorithm for bin packing
• (Probably) the minimum sum of squares
• Algorithm NextFit for the bin packing problem
• Interior-point-based online stochastic bin packing
• Adaptive Bin Packing with Overflow
• A service system with packing constraints: greedy randomized algorithm achieving sublinear in scale optimality gap
• 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
• 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)