TIGHT WORST-CASE PERFORMANCE BOUNDS FOR NEXT-K-FIT BIN PACKING

The bin packing problem is to pack a list of reals in (0, 1] into unit-capacity bins using the minimum number of bins. Let R[A] be the limiting worst value for the ratio A(L)/L* as L* goes to infinity, where A(L) denotes the number of bins used in the approximation algorithm A, and L* denotes the minimum number of bins needed to pack L. Obviously, R[A] reflects the worst-case behavior of A. For Next-k-Fit(NkF for short, k greater-than-or-equal-to 2), which is a linear time approximation algorithm for bin packing, it was known that 1.7 + 3/10(k-1) less-than-or-equal-to R[NkF] less-than-or-equal-to 2. In this paper, a tight bound R[NkF] = 1.7 + 3/10(k-1) is proved.