Tata Institute of Fundamental Research
Weak Epsilon Nets
Seminar
Speaker:
Saurabh Ray (Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 319
66123 Saarbrücken
Germany)
Organiser:
Jaikumar Radhakrishnan
Date:
Monday, 26 Mar 2012, 11:30 to 12:30
Venue:
AG-80
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Saurabh Ray (Max-Planck-Institut für Informatik Department 1: Algorithms and Complexity Campus E1 4, Room 319 66123 Saarbrücken Germany) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Monday, 26 Mar 2012, 11:30 to 12:30 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
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.
I will describe the known results about the weak $epsilon$-net problem and then discuss some partial results and approaches towards improving the bounds.