Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF]. I would like to know what, if anything, such a lower bound implies about the approximability of the associated Set Cover/Hitting Set problems.

To be slightly more specific, consider a family of range spaces, for example, the family:

$\big\{(X,\mathcal{R})$ : $X$ is a finite planar point set, $\mathcal{R}$ contains all intersections of $X$ with lines$\big\}$

If, for some function $f$ that is linear or super-linear, the family contains a range space that does not admit $\epsilon$-nets of size $f(1/\epsilon)$, what, if anything, does this imply about the Minimum Hitting Set problem restricted to this family of range spaces?


If a range space has $\epsilon$-net of size $f(1/\epsilon)$, then the integrality gap of the fractional hitting set (or set cover) is $f(1/\epsilon)/(1/\epsilon)$. See the work by Philip Long (here [The Even etal. work is later than this work, and rediscover some of his stuff]). See also the slides 13-16 here.

In short, having non-linear $\epsilon$-nets, indicates that approximating the relevant hitting-set/set cover problem within better than a constant factor is going to be very challenging.

  • $\begingroup$ Which section of the first paper is relevant to this particular problem? Or equivalently, in the second link, you say "In geometric settings, there is an $\epsilon$-net of size $O(K/\epsilon)$ iff the integrality gap is $K$." I am having trouble understanding that. $\endgroup$ – taninamdar Oct 23 '15 at 19:22
  • 1
    $\begingroup$ Theorem 1 in the paper.... $\endgroup$ – Sariel Har-Peled Oct 24 '15 at 5:02

I'm not sure it does imply anything. The main results flow in the other direction i.e by the Bronnimann/Goodrich or Even/Rawitz/Shahar constructions, a linear sized net implies a constant factor approximation for the hitting set (for bounded VC dimension),


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.