BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-78-662
       ENTRY:: June 22, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: New algorithms in bin packing
        TYPE:: Technical Report
      AUTHOR:: Yao, Andrew Chi-Chih
        DATE:: September 1978
       PAGES:: 52
    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.
       NOTES:: [Adminitrivia V1/Prg/19950622]
         END:: STAN//CS-TR-78-662