New worst-case results for the bin-packing problem

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.