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 greater than or equal to 3, settling a n open question from the recent survey by Coffman. Garey, and Johnson ["App roximation algorithms for bin backing: A survey," Ap proximation algorithms for NP-hard problems, D. Hochbaum (Editor), PWS, Boston, 1996]. Our proof generalizes the multidimensional Markov chain analysis used by Kenyon, Sinc lair, and Rabani to prove that Best Fit is also stable under these distribu tions [Proc Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1995, pp. 351-358]. Our proof is motivated by an analysis of Random Fit, a new s imple packing algorithm related to First Fit, that is interesting in its ow n right. We show that Random Fit is stable under the input distributions Il (k - 2, k), as well as present worst case bounds and some results on distri butions U {k - 1, k} and U {k, k} For Random Fit. (C) 2000 John Wiley & Son s, Inc.