BIASED RANDOM-WALKS, LYAPUNOV FUNCTIONS, AND STOCHASTIC-ANALYSIS OF BEST FIT BIN PACKING

We study the average case performance of the Best Fit algorithm for on -line bin packing under the distribution U{j,k}, in which the item siz es are uniformly distributed in the discrete range {1/k, 2/k,....j/k}. Our main result is that, in the case j = k - 2, the expected waste fo r an infinite stream of items remains bounded. This settles an open pr oblem posed by Coffman et al. [4]. It is also the first result which i nvolves a detailed analysis of the infinite multidimensional Markov ch ain underlying the algorithm. (C) 1998 Academic Press.