Probabilistic Analysis of Bin Packing Heuristics
Hoon Liong Ong, M. J. Magazine, T. S. Wee
Operations Research · 1984 · Volume 32 · Issue 5
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
Enable JavaScript for citation tools and additional paper interactions.