Optimal Bin Packing with Items of Random Sizes

Abstract

Consider a probability μ on [0, 1] and i.i.d. random variables X 1 , X 2 , …, X n distributed like μ. Let Q n denote the optimal (minimum) number of unit size bins needed to pack items of size X 1 , X 2 , …, X n . We characterize the class of μ which have the property that lim n→∞ Q n /n = E(X 1 ) a.s., or equivalently that the expected level of occupancy of bins converges to one.