New worst‐case results for the bin‐packing problem
David Simchi‐Levi
Naval Research Logistics (NRL), 1994, vol. 41, issue 4, 579-585
Abstract:
In this note we consider the familiar bin‐packing problem and provide new worst‐case results for a number of classical heuristics. We show 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 P = NP. © 1994 John Wiley & Sons, Inc.
Date: 1994
References: View complete reference list from CitEc
Citations:
Downloads: (external link)
https://doi.org/10.1002/1520-6750(199406)41:43.0.CO;2-G
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:41:y:1994:i:4:p:579-585
Access Statistics for this article
More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().