Packing random rectangles

E. G. Coffman, George S. Lueker, Joel Spencer, Peter M. Winkler

Research output: Contribution to journalArticlepeer-review

Abstract

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 Cn of items in a maximum cardinality disjoint subset of n random rectangles satisfies n1/2/K ≤ ECn ≤ Kn1/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, n1/2/K ≤ ECn ≤ K (n logd-1 n)1/2. Finally, for a certain distribution of random cubes we show that for some absolute constant K, the number Qn of items in a maximum cardinality disjoint subset of the cubes satisfies nd/(d+1)/K ≤ EQn ≤ Knd/(d+1).

Original languageEnglish (US)
Pages (from-to)585-599
Number of pages15
JournalProbability Theory and Related Fields
Volume120
Issue number4
DOIs
StatePublished - Aug 2001

Keywords

  • 2-dimensional packing
  • Independent sets
  • Intersection graphs
  • Probabilistic analysis of optimization problems
  • n-dimensional packing

ASJC Scopus subject areas

  • Analysis
  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Packing random rectangles'. Together they form a unique fingerprint.

Cite this