The average-case analysis of some on-line algorithms for bin packing (Q1100912)

In this paper we give tighter bounds than were previously known for the performance of the bin packing algorithms Best Fit and First Fit when the inputs are uniformly distributed on [0,1]. We also give a general lower bound for the performance of any on-line bin packing algorithm on this distribution. We prove these results by analyzing optimal matchings on points randomly distributed in a unit square. We give a new lower bound for the up-right matching problem.