Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR11-019 | 5th February 2011 03:57

#### On the Approximability of a Geometric Set Cover Problem

TR11-019
Authors: Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni
Publication: 11th February 2011 10:07
Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case of the set covering problem where the family of subsets given can be taken as a set of intersections of the straight line segments in $S$. Requiring that the given subsets can be interpreted geometrically this way is a major restriction on the input, yet we have shown that the problem is still strongly NP-complete. In light of this result, we studied the performance of two polynomial-time approximation algorithms which return segment coverings. We obtain certain theoretical results, and in particular we show that the performance ratio for each of these algorithms is unbounded, in general.