Abstract
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/17 ≈ 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.
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/17 ≈ 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.
| Original language | English |
|---|---|
| Journal | Discrete Applied Mathematics |
| Volume | 160 |
| Pages (from-to) | 1914-1923 |
| Number of pages | 10 |
| ISSN | 0166-218X |
| DOIs | |
| Publication status | Published - 2012 |