PACKING RANDOM INTERVALS
成果类型：
Article
署名作者：
Rhee, Wansoo T.; Talagrand, Michel
署名单位：
University System of Ohio; Ohio State University; University System of Ohio; Ohio State University; Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS)
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
发表日期：
1996
页码：
572-576
关键词：
摘要：
A packing of a collection of subintervals of [0,1] is a pairwise disjoint subcollection of the intervals; its wasted space is the measure of the set of points not covered by the packing. Consider n random intervals, I-1,...,I-n , chosen by selecting endpoints independently from the uniform distribution. We strengthen and simplify the results of Coffman, Poonen and Winkler, and we show that, for some universal constant K and for each t >= 1, with probability greater than or equal to 1 - 1/n(t), there is a packing with wasted space less than or equal to Kt(log n)(2)/n.