Improved Approximation Algorithms for Geometric Set Cover |
| |
Authors: | Kenneth L Clarkson Kasturi Varadarajan |
| |
Institution: | (1) Bell Labs, 600 Mountain Avenue, Murray Hill, NJ 07974, USA;(2) University of Iowa, 101E, MacLean Hall, Iowa City, IA 52241, USA |
| |
Abstract: | Given a collection S of subsets of some set
and
the set cover problem is to find the smallest subcollection
that covers
that is,
where
denotes
We assume of course that S covers
While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where usually
Combining previously known techniques 4], 5], we show that polynomial-time approximation algorithms with provable performance
exist, under a certain general condition: that for a random subset
and nondecreasing function f(·), there is a decomposition of the complement
into an expected at most f(|R|) regions, each region of a particular simple form. Under this condition, a cover of size O(f(|C|))
can be found in polynomial time. Using this result, and combinatorial geometry results implying bounding functions f(c) that
are nearly linear, we obtain o(log c) approximation algorithms for covering by fat triangles, by pseudo-disks, by a family
of fat objects, and others. Similarly, constant-factor approximations follow for similar-sized fat triangles and fat objects,
and for fat wedges. With more work, we obtain constant-factor approximation algorithms for covering by unit cubes in
and for guarding an x-monotone polygonal chain. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|