Geometric set cover problem

The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space $\Sigma =(X,{\mathcal {R}})$ where $X$ is a universe of points in $\mathbb {R} ^{d}$ and ${\mathcal {R}}$ is a family of subsets of $X$ called ranges, defined by the intersection of $X$ and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset ${\mathcal {C}}\subseteq {\mathcal {R}}$ of ranges such that every point in the universe $X$ is covered by some range in ${\mathcal {C}}$ .

Given the same range space $\Sigma$ , a closely related problem is the geometric hitting set problem, where the goal is to select a minimum-size subset $H\subseteq X$ of points such that every range of ${\mathcal {R}}$ has nonempty intersection with $H$ , i.e., is hit by $H$ .

In the one-dimensional case, where $X$ contains points on the real line and ${\mathcal {R}}$ is defined by intervals, both the geometric set cover and hitting set problems can be solved in polynomial time using a simple greedy algorithm. However, in higher dimensions, they are known to be NP-complete even for simple shapes, i.e., when ${\mathcal {R}}$ is induced by unit disks or unit squares.^[1]The discrete unit disc cover problem is a geometric version of the general set cover problem which is NP-hard.^[2]

Many approximation algorithms have been devised for these problems. Due to the geometric nature, the approximation ratios for these problems can be much better than the general set cover/hitting set problems. Moreover, these approximate solutions can even be computed in near-linear time.^[3]

Approximation algorithms

The greedy algorithm for the general set cover problem gives $O(\log n)$ approximation, where $n=\max\{|X|,|{\mathcal {R}}|\}$ . This approximation is known to be tight up to constant factor.^[4] However, in geometric settings, better approximations can be obtained. Using a multiplicative weight algorithm,^[5] Brönnimann and Goodrich^[6] showed that an $O(\log {\mathsf {OPT}})$ -approximate set cover/hitting set for a range space $\Sigma$ with constant VC-dimension can be computed in polynomial time, where ${\mathsf {OPT}}\leq n$ denotes the size of the optimal solution. The approximation ratio can be further improved to $O(\log \log {\mathsf {OPT}})$ or $O(1)$ when ${\mathcal {R}}$ is induced by axis-parallel rectangles or disks in $\mathbb {R} ^{2}$ , respectively.

Near-linear-time algorithms

Based on the iterative-reweighting technique of Clarkson^[7] and Brönnimann and Goodrich,^[6] Agarwal and Pan^[3] gave algorithms that computes an approximate set cover/hitting set of a geometric range space in $O(n~\mathrm {polylog} (n))$ time. For example, their algorithms computes an $O(\log \log {\mathsf {OPT}})$ -approximate hitting set in $O(n\log ^{3}n\log \log \log {\mathsf {OPT}})$ time for range spaces induced by 2D axis-parallel rectangles; and it computes an $O(1)$ -approximate set cover in $O(n\log ^{4}n)$ time for range spaces induced by 2D disks.

References

↑ Fowler, R.J.; Paterson, M.S.; Tanimoto, S.L. (1981), "Optimal packing and covering in the plane are NP-complete", Inf. Process. Lett.
↑ https://cs.uwaterloo.ca/~alopez-o/files/OtDUDCP_2011.pdf On the Discrete Unit Disk Cover Problem
1 2 Agarwal, Pankaj K.; Pan, Jiangwei (2014). "Near-Linear Algorithms for Geometric Hitting Sets and Set Covers". Proceedings of the thirtieth annual symposium on Computational Geometry.
↑ Feige, Uriel (1998), "A threshold of ln n for approximating set cover", Journal of the ACM
↑ Arora, S.; Hazan, E.; Kale, S. (2012), "The Multiplicative Weights Update Method: a Meta-Algorithm and Applications", Theory of Computing
1 2 Brönnimann, H.; Goodrich, M. (1995), "Almost optimal set covers in finite VC-dimension", Discrete & Computational Geometry
↑ Clarkson, Kenneth L. (1993-08-11). Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; et al., eds. Algorithms for polytope covering and approximation. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 246–252. doi:10.1007/3-540-57155-8_252. ISBN 978-3-540-57155-1.

This article is issued from Wikipedia - version of the 11/15/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Geometric set cover problem

Approximation algorithms

Near-linear-time algorithms

See also

References