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


   Data protection at SDUDatabeskyttelse på SDU