Finding small hitting sets in infinite range spaces of bounded VC-Dimension

We consider the problem of finding a small hitting set in an infinite range space F = (Q, R) 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(sF(z^∗_F) that hits (1 - δ)-fraction of R (with respect to a given measure) in time proportional to log(1δ), where sF(1/ϵ) is the size of the smallest ϵ-net the range space admits, and z^∗_F is the value of the fractional optimal solution. This exponentially improves upon previous results which achieve the same approximation guarantees with running time proportional to poly(1/δ). Our assumptions hold, for instance, in the case when the range space represents the visibility regions of a polygon in ℝ² giving thus a deterministic polynomial-time O (log z^∗_F) -approximation algorithm for guarding (1 - δ)-fraction of the area of any given simple polygon, with running time proportional to polylog(1/δ).