Worst-Case Analysis of Heuristics for the Bin Packing Problem with General Cost Structures

Shoshana Anily, Julien Bramel and David Simchi-Levi
Additional contact information
Shoshana Anily: Tel Aviv University, Tel Aviv, Israel
Julien Bramel: Columbia University, New York, New York
David Simchi-Levi: Columbia University, New York, New York

Operations Research, 1994, vol. 42, issue 2, 287-298

Abstract: We consider the famous bin packing problem where a set of items must be stored in bins of equal capacity. In the classical version, the objective is to minimize the number of bins used. Motivated by several optimization problems that occur in the context of the storage of items, we study a more general cost structure where the cost of a bin is a concave function of the number of items in the bin. The objective is to store the items in such a way that total cost is minimized. Such cost functions can greatly alter the way the items should be assigned to the bins. We show that some of the best heuristics developed for the classical bin packing problem can perform poorly under the general cost structure. On the other hand, the so-called next-fit increasing heuristic has an absolute worst-case bound of no more than 1.75 and an asymptotic worst-case bound of 1.691 for any concave and monotone cost function. Our analysis also provides a new worst-case bound for the well studied next-tit decreasing heuristic when the objective is to minimize the number of bins used.

Keywords: analysis of algorithms: heuristics and worst-case analysis; mathematics: bin packing and combinatorial optimization (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.2.287 (application/pdf)

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:inm:oropre:v:42:y:1994:i:2:p:287-298

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().