首页 | 本学科首页   官方微博 | 高级检索  
     


Convergence of optimal stochastic bin packing
Authors:Wansoo T Rhee
Affiliation:Faculty of Management Sciences, The Ohio State University, Columbus, OH 43210, USA
Abstract:Consider independent identically distributed random variables (Xi) valued in [0,1]. Let B(n) be the optimal (minimum) number of unit size bins needed to pack n items of size X1, X2,…,Xn. We prove that there exists a numerical constant C such that for t > 0,
Pr(∣B(n)?E(B(n))∣>tn)≤ C exp(? t).
The constant C does not depend on the distribution of X.
Keywords:bin packing  convergence  random variables
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号