Optimal Bin Packing with Items of Random Sizes
- 1 February 1988
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 13 (1) , 140-151
- https://doi.org/10.1287/moor.13.1.140
Abstract
Consider a probability μ on [0, 1] and i.i.d. random variables X1, X2, …, Xn distributed like μ. Let Qn denote the optimal (minimum) number of unit size bins needed to pack items of size X1, X2, …, Xn. We characterize the class of μ which have the property that limn→∞ Qn/n = E(X1) a.s., or equivalently that the expected level of occupancy of bins converges to one.Keywords
This publication has 0 references indexed in Scilit: