Weak Epsilon Nets

Given a set $P$ of $n$ points in $R^d$, a weak $epsilon$-net of $P$ with respect to convex sets in a subset of $R^d$ that intersects every convex set containing an $epsilon$-fraction of the points in $P$. Finding optimal bounds for the size of a weak $epsilon$-net is a fundamental problem in discrete and convex geometry and has been an open problem for 25 years. While we have a very good understanding of strong $epsilon$-nets, there is huge gap in the known bounds for weak $epsilon$-nets. The current upper bound is $O(epsilon^{-d} polylog epsilon^{-1})$ while the lower bound is $Omega( epsilon^{-1} log^{d-1} epsilon^{-1})$. Both weak and strong $epsilon$-nets have been used as rounding procedures for various set-cover type problems. Better bounds for their sizes therefore translate to improved bounds on integrality gaps of these problems.

I will describe the known results about the weak $epsilon$-net problem and then discuss some partial results and approaches towards improving the bounds.