PACKING ITEMS FROM A TRIANGULAR DISTRIBUTION

作     者：KRAUSE, K LARMORE, LL VOLPER, DJ 

作者机构：Dep. Inf. and Comp. Sci. Univ. California Irvine CA 92717 USA 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1987年第25卷第6期

页      面：351-361页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation, NSF, (DCR-85-09667) National Science Foundation, NSF Natural Science Foundation of Jiangsu Province, (MCS-81-05911) Natural Science Foundation of Jiangsu Province 

主　　题：Bin-packing probabilistic algorithm 

摘      要：The authors consider the problem of packing n items, which are drawn according to a probability distribution whose density function is triangular in shape, into bins of unit capacity. For triangles which represent density functions whose expectation is 1/p for p = 3, 4, 5,..., they give a packing strategy for which the ratio of the number of bins used in the packing to the expected total size of the items asymptotically approaches 1.