Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-dimension
arXiv:1610.03812
Abstract
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 , a set of size $O(s_{\cF}(z^*_\cF))$ that hits -fraction of $\cR$ (with respect to a given measure) in time proportional to , where $s_{\cF}(\frac{1}ε)$ 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(\frac{1}δ)$. Our assumptions hold, for instance, in the case when the range space represents the {\it visibility} regions of a polygon in $\RR^2$, giving thus a deterministic polynomial time $O(\log z^*_{\cF})$-approximation algorithm for guarding -fraction of the area of any given simple polygon, with running time proportional to $\polylog(\frac{1}δ)$.