Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > WORST CASE PERFORMANCE:
Reports tagged with worst case performance:
TR11-019 | 5th February 2011
Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni

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 ... more >>>




ISSN 1433-8092 | Imprint