**Tight results for Next Fit and Worst Fit with resource augmentation***Joan Boyar, Leah Epstein, Asaf Leven*

Theoretical Computer Science 2010

It is well known that the two simple algorithms for the classic bin packing problem, Next Fit and Worst Fit both have an approximation ratio of 2. However, Worst Fit seems to be a more reasonable algorithm, since it never opens a new bin if an existing bin can still be used.

Using resource augmented analysis, where the output of an
approximation algorithm, which can use bins of size b>1, is
compared to an optimal packing into bins of size 1, we give a
*complete analysis* of the asymptotic approximation ratio of
Worst Fit and of Next Fit, and use it to show that Worst Fit is strictly better
than Next Fit for any 1 < b < 2, while they have the same asymptotic
performance guarantee for all b >= 2, and for b=1.

Last modified: Thu Mar 4 09:20:14 CET 2010 Joan Boyar (joan@imada.sdu.dk)