10
$\begingroup$

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?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Oct 23, 2015 at 19:22
  • 1
    $\begingroup$ Theorem 1 in the paper.... $\endgroup$
    – Sariel Har-Peled
    Commented Oct 24, 2015 at 5:02
5
$\begingroup$

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),

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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