All-Around Near-Optimal Solutions for the Online Bin Packing Problem

DOI10.1007/978-3-662-48971-0_61MaRDI QIDQ3459910zbMATH OpenOpenAlexFDO

Authors Shahin Kamali, Alejandro Lopez-Ortiz

Publication date 11 January 2016

Published in Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

Abstract: In this paper we present the first algorithm with optimal average-case and close-to-best known worst-case performance for the classic on-line problem of bin packing. It has long been observed that known bin packing algorithms with optimal average-case performance were not optimal in the worst-case sense. In particular First Fit and Best Fit had optimal average-case ratio of 1 but a worst-case competitive ratio of 1.7. The wasted space of First Fit and Best Fit for a uniform random sequence of length $n$ is expected to be $Theta(n^{2/3})$ and $Theta(sqrtnlo{g}^{3/4}n)$, respectively. The competitive ratio can be improved to 1.691 using the Harmonic algorithm; further variations of this algorithm can push down the competitive ratio to 1.588. However, Harmonic and its variations have poor performance on average; in particular, Harmonic has average-case ratio of around 1.27. In this paper, first we introduce a simple algorithm which we term Harmonic Match. This algorithm performs as well as Best Fit on average, i.e., it has an average-case ratio of 1 and expected wasted space of $Theta(sqrtnlo{g}^{3/4}n)$. Moreover, the competitive ratio of the algorithm is as good as Harmonic, i.e., it converges to $1.691$ which is an improvement over 1.7 of Best Fit and First Fit. We also introduce a different algorithm, termed as Refined Harmonic Match, which achieves an improved competitive ratio of $1.636$ while maintaining the good average-case performance of Harmonic Match and Best Fit. Finally, our extensive experimental evaluation of the studied bin packing algorithms shows that our proposed algorithms have comparable average-case performance with Best Fit and First Fit, and this holds also for sequences that follow distributions other than the uniform distribution.

Recommendations

• scientific article; zbMATH DE number 1756012
• On the online bin packing problem
• An asymptotic competitive scheme for online bin packing
• An asymptotic competitive scheme for online bin packing
• Online bin packing: old algorithms and new results
• An optimal online algorithm for bounded space variable-sized bin packing
• scientific article; zbMATH DE number 1670831
• Online bin packing problem with buffer and bounded size revisited
• Online bin packing with cardinality constraints resolved
• Online bin packing with cardinality constraints resolved

Cited in

(11)

• Average-case analysis of the smart next fit algorithm
• The optimal absolute ratio for online bin packing
• Models for video-on-demand scheduling with costs
• Sparse, continuous policy representations for uniform online bin packing via regression of interpolants
• On the online bin packing problem
• Beating the harmonic lower bound for online bin packing
• scientific article; zbMATH DE number 4773 (Why is no real title available?)
• Best fit bin packing with random order revisited
• Tighter bounds for the harmonic bin packing algorithm
• Lower bounds for several standard bin packing algorithms in the random order model
• An asymptotic competitive scheme for online bin packing

This page was built for publication: All-Around Near-Optimal Solutions for the Online Bin Packing Problem

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