1985/07/01 by C. C. Lee, D. T. Lee · 6 citations
Engineering · Computer Science · Mathematics · #Optimization and Packing Problems #Computational Geometry and Mesh Generation #graph theory and CDMA systems #Bin packing problem #Algorithm #Bin #Simple (philosophy) #Space (punctuation) #Line (geometry) #Combinatorics #Mathematics #Upper and lower bounds #SIMPLE algorithm #Harmonic #Binary logarithm #Computer science #Physics #Geometry #Mathematical analysis
paper · pdf · doi:10.1145/3828.3833
openalex publication_date 1985/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The one-dimensional on-line bin-packing problem is considered, A simple O (1)-space and O ( n )-time algorithm, called HARMONIC M , is presented. It is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the O ( n )-space and O ( n log n )-time algorithm FIRST FIT. Also shown is that 1.691 … is a lower bound for all 0 (1)-space on-line bin-packing algorithms. Finally a revised version of HARMONIC M , an O ( n )-space and O ( n )- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636.