Institution: Stanford University, Department of Computer Science

Title: New algorithms in bin packing

Author: Yao, Andrew Chi-Chih

Date: September 1978

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. In this paper we give an on-line O(n log n)-time algorithm RFF with r(RFF) = 5/3, and an off-line polynomial-time algorithm RFFD with r(RFFD) = (11/9)-$\epsilon$ for some fixed $\epsilon$ > 0. 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) $\geq$ 3/2. We also discuss the question "how well can an O(n)-time algorithm perform?", showing that, in the generalized d-dimensional bin-packing, any O(n)-time algorithm S must have r(S) $\geq$ d.

http://i.stanford.edu/pub/cstr/reports/cs/tr/78/662/CS-TR-78-662.pdf