PACKING RANDOM INTERVALS
成果类型：
Article
署名作者：
COFFMAN, EG; POONEN, B; WINKLER, P
署名单位：
Nokia Corporation; Nokia Bell Labs; AT&T
刊物名称：
PROBABILITY THEORY AND RELATED FIELDS
ISSN/ISSBN：
0178-8051
DOI：
10.1007/BF01295224
发表日期：
1995
页码：
105-121
关键词：
摘要：
Let n random intervals I-1,...,I-n be chosen by selecting endpoints independently from the uniform distribution on [0,1]. A packing is a pairwise disjoint subset of the intervals; its wasted space is the Lebesgue measure of the points of [0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for large n, this ''best'' packing has wasted space O(log2n/n). It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced to O(1/n). Interestingly, there is a striking difference between the sizes of the best packings: about log n intervals in the unit interval case, but usually only one or two arcs in the circle case.
来源URL：