Convergence of optimal stochastic bin packing (Q1062627)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Convergence of optimal stochastic bin packing |
scientific article |
Statements
Convergence of optimal stochastic bin packing (English)
0 references
1985
0 references
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.
0 references
bin packing
0 references
convergence
0 references
cutting stock
0 references
random variables
0 references
0 references