Probabilistic Analysis of Bin Packing Heuristics

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.