####
Average-case analyses of first-fit and random-fit bin packing

We prove that the First Fit bin packing algorithm is stable under the
input distribution U{k-2, k} for all k > 3, settling an open question
from the recent survey by Coffman, Garey, and Johnson. Our proof
generalizes the multidimensional Markov chain analysis used by Kenyon,
Sinclair, and Rabani to prove that Best Fit is also stable under these
distributions. Our proof is motivated by an analysis
of Random Fit, a new simple packing algorithm related to First Fit,
that is interesting in its own right. We show that Random Fit is
stable under the input distributions U{k-2, k}, as well as present
worst case bounds and some results on distributions U{k-1, k} and U{k,
k} for Random Fit.