# Consequences of lower bounds for $\epsilon$-nets on approximation

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?

• there's a new result out that has even stronger lower bounds: arxiv.org/abs/1012.1240 Dec 7, 2010 at 6:32

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.
• 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. Oct 23, 2015 at 19:22