<p>I'm not sure it does imply anything. The main results flow in the other direction i.e by the <a href="http://www.cs.jhu.edu/~goodrich/cgc/pubs/cover.ps.gz">Bronnimann/Goodrich</a> or <a href="http://www.eng.tau.ac.il/~guy/Papers/VC.pdf">Even/Rawitz/Shahar</a> constructions, a linear sized net implies a constant factor approximation for the hitting set (for bounded VC dimension), </p>

CC BY-SA 2.5
2010-09-15T04:26:39.833Z
2010-09-15T04:26:39.833Z
Suresh Venkat
<p>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 (<a href="http://www.phillong.info/publications/intprog.pdf">here</a> [The Even etal. work is later than this work, and rediscover some of his stuff]). See also the slides 13-16 <a href="http://valis.cs.uiuc.edu/~sariel/papers/10/haystacks/haystack.pdf">here</a>. </p>

<p>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. </p>

CC BY-SA 3.0
2015-10-23T19:22:37.137Z
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.
taninamdar
CC BY-SA 3.0
2015-10-24T05:02:26.903Z
Theorem 1 in the paper....
Sariel Har-Peled
CC BY-SA 2.5
2010-09-24T15:52:48.030Z
2010-09-24T23:48:48.213Z
2010-09-24T23:48:48.213Z
Sariel Har-Peled
<p>Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting <a href="http://www.tau.ac.il/~nogaa/PDFS/epsnet3.pdf">[PDF]</a>.  I would like to know what, if anything, such a lower bound implies about the approximability of the associated Set Cover/Hitting Set problems.  </p>

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

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

<p>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?</p>

CC BY-SA 2.5
2010-12-07T06:32:36.630Z
there's a new result out that has even stronger lower bounds: http://arxiv.org/abs/1012.1240
Suresh Venkat
<cg.comp-geom><set-cover><hypergraphs><approximation-hardness><epsilon-nets>
Consequences of lower bounds for $\epsilon$-nets on approximation
James King
# Consequences of lower bounds for $\epsilon$-nets on approximation

(Asked by: username_0 on 2010-09-14)

Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [[PDF]](http://www.tau.ac.il/~nogaa/PDFS/epsnet3.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?

**Tags:** cg.comp-geom, set-cover, hypergraphs, approximation-hardness, epsilon-nets
> **Comments:**
> **username_1**: there's a new result out that has even stronger lower bounds: http://arxiv.org/abs/1012.1240  

---

## 2 answers

### Answer by username_2 on 2010-09-24. Score: 7 | Accepted answer

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](http://www.phillong.info/publications/intprog.pdf) [The Even etal. work is later than this work, and rediscover some of his stuff]). See also the slides 13-16 [here](http://valis.cs.uiuc.edu/~sariel/papers/10/haystacks/haystack.pdf).

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.

> **Comments:**
> **username_3**: 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.  
> **username_2**: Theorem 1 in the paper....  

---

### Answer by username_1 on 2010-09-15. Score: 5

I'm not sure it does imply anything. The main results flow in the other direction i.e by the [Bronnimann/Goodrich](http://www.cs.jhu.edu/~goodrich/cgc/pubs/cover.ps.gz) or [Even/Rawitz/Shahar](http://www.eng.tau.ac.il/~guy/Papers/VC.pdf) constructions, a linear sized net implies a constant factor approximation for the hitting set (for bounded VC dimension),


---

