**On the Absolute Approximation Ratio for First Fit and Related Results***Joan Boyar, György Dósa, Leah Epstein*

Discrete Applied Mathematics.

We revisit three famous bin packing algorithms, namely Next Fit (NF), Worst Fit (WF) and First Fit (FF).

We compare the approximation ratio of these algorithms as a function of the total size of the input items α. We give a complete analysis of the worst case behavior of WF and NF, and determine the ranges of α for which FF has a smaller approximation ratio than WF and NF.

In addition, we prove a new upper bound of 12/7 ≈ 1.7143 on the absolute approximation ratio of FF, improving over the previously known upper bound of 1.75, given by Simchi-Levi. This property of FF is in contrast to the absolute approximation ratios of WF and NF, which are both equal to 2.

Last modified: Tue Apr 17 08:34:28 CEST 2012