On Covering Problems of Rado |
| |
Authors: | Sergey Bereg Adrian Dumitrescu Minghui Jiang |
| |
Affiliation: | (1) IBM T. J. Watson Research Center and MIT, 32-221, 1101 Kitchawan Road, Yorktown Heights, NY 10598, USA;(2) MIT Sloan School of Management, 50 Memorial Drive, Cambridge, MA 02139-4307, USA |
| |
Abstract: | T. Rado conjectured in 1928 that if ℱ is a finite set of axis-parallel squares in the plane, then there exists an independent
subset ℐ⊆ℱ of pairwise disjoint squares, such that ℐ covers at least 1/4 of the area covered by ℱ. He also showed that the
greedy algorithm (repeatedly choose the largest square disjoint from those previously selected) finds an independent set of
area at least 1/9 of the area covered by ℱ. The analogous question for other shapes and many similar problems have been considered
by R. Rado in his three papers (in Proc. Lond. Math. Soc. 51:232–264, 1949; 53:243–267, 1951; and J. Lond. Math. Soc. 42:127–130, 1968) on this subject. After 45 years, Ajtai (in Bull. Acad. Polon. Sci. Sér. Sci. Math. Astron. Phys. 21:61–63, 1973) came up with a surprising example disproving T. Rado’s conjecture. We revisit Rado’s problem and present improved upper
and lower bounds for squares, disks, convex bodies, centrally symmetric convex bodies, and others, as well as algorithmic
solutions to these variants of the problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|