2016/10/12 by Khaled Elbassioni, Elbassioni, Khaled · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1610.03812
We consider the problem of finding a small hitting set in an \it infinite range space \cF=(Q,\cR) of bounded VC-dimension. We show that, under reasonably general assumptions, the infinite dimensional convex relaxation can be solved (approximately) efficiently by multiplicative weight updates. As a consequence, we get an algorithm that finds, for any δ>0, a set of size O(s\cF(z^*_\cF)) that hits (1-δ)-fraction of \cR (with respect to a given measure) in time proportional to log(\frac1δ), where s\cF(\frac1ε) is the size of the smallest ε-net the range space admits, and z^*\cF is the value of the \it fractional optimal solution. This \it exponentially improves upon previous results which achieve the same approximation guarantees with running time proportional to \poly(\frac1δ). Our assumptions hold, for instance, in the case when the range space represents the \it visibility regions of a polygon in \RR2, giving thus a deterministic polynomial time O(log z^*\cF)-approximation algorithm for guarding (1-δ)-fraction of the area of any given simple polygon, with running time proportional to \polylog(\frac1δ).