Title: Optimal Bin Packing with Items of Random Sizes
Abstract: Consider a probability μ on [0, 1] and i.i.d. random variables X 1 , X 2 , …, X n distributed like μ. Let Q n denote the optimal (minimum) number of unit size bins needed to pack items of size X 1 , X 2 , …, X n . We characterize the class of μ which have the property that lim n→∞ Q n /n = E(X 1 ) a.s., or equivalently that the expected level of occupancy of bins converges to one.
Publication Year: 1988
Publication Date: 1988-02-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 46
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot