BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/260
DTSTAMP:20230914T125917Z
SUMMARY:Weak Epsilon Nets
DESCRIPTION:Speaker: Saurabh Ray (Max-Planck-Institut für Informatik\nDepa
 rtment 1: Algorithms and Complexity\nCampus E1 4\, Room 319\n66123 Saarbr
 ücken\nGermany)\n\nAbstract: \nGiven 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$-ne
 t 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 str
 ong $epsilon$-nets\, there is huge gap in the known bounds for weak $epsil
 on$-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 therefo
 re translate to improved bounds on integrality gaps of these problems.\n\n
 I will describe the known results about the weak $epsilon$-net problem and
  then discuss some partial results and approaches towards improving the bo
 unds.\n
URL:https://www.tcs.tifr.res.in/web/events/260
DTSTART;TZID=Asia/Kolkata:20120326T113000
DTEND;TZID=Asia/Kolkata:20120326T123000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR