A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces

We consider the problem of finding a minimum-size hitting set in a range space F=(Q,R) defined by a measure on a family of subsets of an infinite set R. We observe 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(α_Fz_F^⁎) that hits a (1−δ)-fraction of the ranges in R (with respect to the given measure) in time proportional to log⁡[Formula presented], where z_F^⁎ is the value of the fractional optimal solution and α_F is the integrality gap of the standard LP relaxation of the hitting set problem for the restriction of F on a set of points of size O(z_F^⁎log⁡[Formula presented]). Some applications of this result in Computational Geometry are given.