| Article ID: | iaor20043268 |
| Country: | Netherlands |
| Volume: | 32 |
| Issue: | 2 |
| Start Page Number: | 159 |
| End Page Number: | 166 |
| Publication Date: | Mar 2004 |
| Journal: | Operations Research Letters |
| Authors: | Pferschy Ulrich, Caprara Alberto |
| Keywords: | combinatorial analysis |
We analyze the worst-case ratio of a natural heuristic for the bin packing problem, which proceeds by filling one bin at a time, each as much as possible. We show a nontrivial upper bound on this ratio of 4/3+ln4/3=1.6210…, almost matching a known lower bound.