| Article ID: | iaor19942304 |
| Country: | United States |
| Volume: | 41 |
| Issue: | 4 |
| Start Page Number: | 579 |
| End Page Number: | 585 |
| Publication Date: | Jun 1994 |
| Journal: | Naval Research Logistics |
| Authors: | Simchi-Levi David |
| Keywords: | bin packing |
This note considers the familiar bin-packing problem and provides new worst-case results for a number of classical heuristics. It shows that the first-fit and best-fit heuristics have an absolute performance ratio of no more than 1.75, and first-fit decreasing and best-fit decreasing heuristics have an absolute performance ratio of 1.5. The latter is the best possible absolute performance ratio for the bin-packing problem, unless