Convergence of optimal stochastic bin packing (Q1062627)

Consider independent identically distributed random variables \((X_ i)\) valued in [0,1]. Let B(n) be the optimal (minimum) number of unit size bins needed to pack n items of size \(X_ 1,X_ 2,...,X_ n\). We prove that there exists a numerical constant C such that for \(t>0\), Pr(\(| B(n)-E(B(n))| >t\sqrt{n})\leq C\) exp(-t). The constant C does not depend on the distribution of X.