On Line Bin Packing with Items of Random Size

Consider an i.i.d. sequence of random variables X₁, …, 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₁, …, X_n. We prove the existence of an on line algorithm, dependent on μ, that packs X₁, …, X_n in nc(μ) + O(n^1/2(log n)^3/4) bins.