Some distributions that allow perfect packing
- 1 June 1988
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 35 (3) , 564-578
- https://doi.org/10.1145/44483.44487
Abstract
A probability distribution μ on [0, 1] allows perfect packing if n items of size X 1 , … , X n , independent and identically distributed according to μ can be packed in unit size bins in such a way that the expected wasted space is o ( n ). A large class of distributions that allow perfect packing is exhibited. As a corollary, the intervals [ a, b ] for which the uniform distribution on [ a, b ] allows perfect packing are determined.Keywords
This publication has 8 references indexed in Scilit:
- Optimal Bin Packing with Items of Random Sizes IISIAM Journal on Computing, 1989
- Optimal Bin Packing with Items of Random SizesMathematics of Operations Research, 1988
- Martingale Inequalities and NP-Complete ProblemsMathematics of Operations Research, 1987
- A bin-packing system for objects with sizes from a finite set: Necessary and sufficient conditions for stability and some applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Measure TheoryPublished by Springer Nature ,1980
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- PROBABILITY MEASURES IN A METRIC GROUPPublished by Elsevier ,1967
- PROBABILITY MEASURES IN A METRIC SPACEPublished by Elsevier ,1967