Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-019 | 5th February 2011 03:57

On the Approximability of a Geometric Set Cover Problem



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.

ISSN 1433-8092 | Imprint