On the Sum-of-Squares algorithm for bin packing

DOI10.1145/1120582.1120583MaRDI QIDQ3546292zbMATH OpenOpenAlexDBLPWikidataFDO

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)

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)

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}.

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

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
• Sum-of-squares heuristics for bin packing and memory allocation
• A service system with packing constraints: greedy randomized algorithm achieving sublinear in scale optimality gap
• 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)