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
    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

    Identifiers