On the online bin packing problem

2002/09/01 by Steven S. Seiden · 2 citations
Engineering · Computer Science · Mathematics · #Optimization and Packing Problems #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Bin packing problem #Bin #Harmonic #Upper and lower bounds #Algorithm #Computer science #Mathematics #Harmonic analysis #Mathematical optimization #Competitive analysis #Mathematical analysis #Physics

paper · doi:10.1145/585265.585269

openalex publication_date 2002/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/11

Abstract

A new framework for analyzing online bin packing algorithms is presented. This framework presents a unified way of explaining the performance of algorithms based on the Harmonic approach. Within this framework, it is shown that a new algorithm, Harmonic++, has asymptotic performance ratio at most 1.58889. It is also shown that the analysis of Harmonic+1 presented in Richey [1991] is incorrect; this is a fundamental logical flaw, not an error in calculation or an omitted case. The asymptotic performance ratio of Harmonic+1 is at least 1.59217. Thus, Harmonic++ provides the best upper bound for the online bin packing problem to date.

Citations

• An improved lower bound for on-line bin packing algorithms
• New Algorithms for Bin Packing
• On-line bin packing in linear time
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• A simple on-line bin-packing algorithm
• A lower bound for on-line bin packing

Cited by

• TIDAL: Recovering Temporal Phase for Cloud Block Storage Placement from LLM-Derived Semantics
• Bin packing problem [wikipedia]