New Algorithms for Bin Packing

Abstract

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 .