BEST-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(infinity)[A] be the limiting worst value for the ratio A(L)/OPT(L) as OPT(L) goes to infinity, where A(L) denotes the number of bins used when the approxim ation algorithm .4 is applied to the list L, and OPT(L) denotes the mi nimum number of bins needed to pack L. For Best-k-Fit (BkF for short, k greater-than-or-equal-to 1), we prove in this paper that R(infinity) [BkF] = 1.7 + 3/10k.