"Average-Case Analysis of First Fit and Random Fit Bin Packing"
Susanne Albers and Michael Mitzenmacher
Note #1997-002, February 21, 1997. 16 pages

We prove that the First Fit bin packing algorithm is stable
under the input distribution U{k-2,k} when k is at least three,
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 
stable under this distribution. Our proof is motivated by an analysis of 
Random Fit, a new simple packing algorithm related to First Fit, which 
we also show is stable under this distribution.