Probabilistic Analysis of Bin Packing Heuristics

Hoon Liong Ong, M. J. Magazine and T. S. Wee
Additional contact information
Hoon Liong Ong: National University of Singapore, Kent Ridge, Singapore
M. J. Magazine: University of Waterloo, Waterloo, Ontario, Canada
T. S. Wee: Canadian Pacific, Ltd., Montreal, Quebec, Canada

Operations Research, 1984, vol. 32, issue 5, 983-998

Abstract: In this paper we present both a probabilistic and statistical analysis of several bin packing heuristics. With mild conditions on the distribution of problem data, we show that the ratio of the expected number of bins packed for these heuristics to the number of elements converges to some constant. This constant can either be derived analytically or estimated through simulation. We analyze the variance in performance of these heuristics, and we further show that as the number of elements, n , increases, the probability that the number of bins required for these heuristics exceeds any fixed percentage of their expected performance goes to zero.

Keywords: 432 bin packing; 561 probabilistic analysis; 632 heuristic algorithms (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.5.983 (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:32:y:1984:i:5:p:983-998

Access Statistics for this article

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