On Line Bin Packing with Items of Random Size

Abstract

Consider an i.i.d. sequence of random variables X 1 , …, X n distributed according to a given distribution μ on [0, 1]. Let c(μ) be the asymptotic optimal packing ratio, i.e., c(μ) = lim n →∞ ET n /n, where T n is the minimum number of unit size bins needed to pack X 1 , …, X n . We prove the existence of an on line algorithm, dependent on μ, that packs X 1 , …, X n in nc(μ) + O(n 1/2 (log n) 3/4 ) bins.