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

✍ Scribed by Susanne Albers; Michael Mitzenmacher

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 202 KB
• Volume: 16
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(200005)16:3<240::aid-rsa2>3.0.co;2-v

✦ Synopsis

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 ["Approximation algorithms for bin backing: A survey," Approximation algorithms for NP-hard problems, D. Hochbaum (Editor), PWS, Boston, 1996]. 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 [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 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.