A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing

1981/06/01 by Brenda S. Baker, E. G. Coffman · 2 citations
Engineering · Mathematics · #Optimization and Packing Problems #Mathematical Approximation and Integration #graph theory and CDMA systems #Bin packing problem #Mathematics #Upper and lower bounds #Combinatorics #Unit (ring theory) #Bin #Mathematical analysis #Algorithm

paper · doi:10.1137/0602019

openalex publication_date 1981/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/11

Abstract

In this note we derive a tight asymptotic bound on the relative performance of the Next-Fit-Decreasing approximation rule for classical one-dimensional bin-packing. The proof provides a novel application of certain well-known sequences of unit fractions. Potential applications are mentioned.

Citations

• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited by

• Next-fit packs a list and its reverse into the same number of bins
• Bin packing problem [wikipedia]