We prove that the First Fit bin packing algorithm is stable under the input distribution U{k-2,k} for all k geq 3, settling an open question from the recent survey by Coffman, Garey, and Johnson. Our proof generalizes the multi-dimensional Markov chain analysis used by Kenyon, Rabani, and Sinclair 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.
Originally appeared in the Proceedings of the 9th Annual ACM Symposium on Discrete Algorithms, pp. 290--299, 1998.