1980/04/01 by Andrew Chi-Chih Yao · 6 citations
Engineering · Computer Science · Mathematics · #Optimization and Packing Problems #Complexity and Algorithms in Graphs #graph theory and CDMA systems #Bin packing problem #Combinatorics #Algorithm #Bin #Time complexity #Mathematics #Line (geometry) #Binary logarithm #Running time #Approximation algorithm #Discrete mathematics #Geometry
paper · pdf · doi:10.1145/322186.322187
openalex publication_date 1980/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
In the bin-packing problem a list L of n numbers are to be packed into unit-capacity bins. For any algorithm S , let r ( S ) be the maximum ratio S ( L )/ L * for large L * , where S ( L ) denotes the number of bins used by S and L * denotes the minimum number needed. An on-line Ο ( n log n )-time algorithm RFF with r (RFF) = 5/3 and an off-line polynomial-time algorithm RFFD with r (RFFD) ≤ 11/9 - ε for some fixed ε > 0, are given. These are strictly better, respectively, than two prominent algorithms: the First-Fit (FF), which is on-line with r (FF) = 17/10, and the First-Fit-Decreasing (FFD) with r (FFD) = 11/9. Furthermore, it is shown that any on-line algorithm S must have r ( S ) ≥ 3/2. The question, “How well can an ο ( n log n )-time algorithm perform?” is also discussed. It is shown that in the generalized d -dimensional bin packing, any ο ( n log n )-time algorithm S must have r ( S ) ≥ d .