Packing random rectangles

• 成果类型: Article
• 署名作者: Coffman, EG Jr; Lueker, GS; Spencer, J; Winkler, PM
• 署名单位: Columbia University; University of California System; University of California Irvine; New York University; Alcatel-Lucent; Lucent Technologies; AT&T
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• 发表日期: 2001
• 页码: 585-599
• 关键词: graphs

摘要

A random rectangle is the product of two independent random intervals, each being the interval between two random points drawn independently and uniformly from [0, 1]. We prove that the number C-n of items in a maximum cardinality disjoint subset of n random rectangles satisfies n(1/2)/K less than or equal to ECn less than or equal to Kn(1/2,) where K is an absolute constant. Although tight bounds for the problem generalized to d > 2 dimensions remain an open problem, we are able to show that, for some absolute constant K, n(1/2)/K less than or equal to ECn less than or equal to K(n log(d-1) n)(1/2.) Finally, for a certain distribution of random cubes we show that for some absolute constant K, the number Q(n) of items in a maximum cardinality disjoint subset of the cubes satisfies n(d/(d+l))/K less than or equal to EQ(n) less than or equal to K-n(d/(d+l).)