×

Inequalities for bin packing. III. (English) Zbl 0820.90079

Summary: [For part II see the author, Math. Oper. Res. 18, No. 3, 685-693 (1993; Zbl 0784.60024).]
Consider the minimum number \(B_ n= B_ n(X_ 1,\dots, X_ n)\) of unit size bins needed to pack items \(X_ 1,\dots, X_ n\) that are independently distributed according to a given distribution \(\mu\) concentrated on \([0, 1]\). We prove that for some universal constant \(K\), we have \[ t\geq K(\log n)^ 2\Rightarrow P(| B_ n- E(B_ n)|\geq t)\leq 2\exp\Biggl(-\min \Biggl({t^ 2\over KnE(X^ 2_ 1)}, {t\over K}\Biggl)\Biggl). \] {}.

MSC:

90C15 Stochastic programming
90C90 Applications of mathematical programming
90C27 Combinatorial optimization
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0784.60024
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Coffman E.G., Probabilistic Analysis of Packing and Partitioning Algorithms (1991) · Zbl 0759.90043
[2] DOI: 10.2307/2282952 · Zbl 0127.10602 · doi:10.2307/2282952
[3] DOI: 10.1080/02331938908843445 · Zbl 0677.60018 · doi:10.1080/02331938908843445
[4] DOI: 10.1137/0219048 · Zbl 0712.90042 · doi:10.1137/0219048
[5] DOI: 10.1287/moor.18.3.685 · Zbl 0784.60024 · doi:10.1287/moor.18.3.685
[6] DOI: 10.1287/moor.12.1.177 · Zbl 0718.60040 · doi:10.1287/moor.12.1.177
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.