SRC Technical Note 1997-002

Average-Case Analysis of First Fit and Random Fit Bin Packing

Susanne Albers and Michael Mitzenmacher

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.

Back to the SRC Technical Notes main page.

• PostScript compressed with UNIX compress -- 128 Kbytes
  
• PostScript compressed with GNU compress (gzip) -- 105 Kbytes
  
• PostScript compressed with ZIP -- 106 Kbytes
  
• PostScript -- 240 Kbytes
  
• Portable Document Format (PDF) -- 168 Kbytes