On the absolute approximation ratio for First Fit and related results

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 127≈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.