Theoretical Computer Science
cg.comp-geom set-cover hypergraphs approximation-hardness epsilon-nets
Updated Sat, 21 May 2022 18:22:19 GMT

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?




Solution

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.





Comments (2)

  • +0 – 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  
  • +1 – Theorem 1 in the paper.... — Oct 24, 2015 at 05:02