BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:On the Single-Pass Streaming Complexity of the Set Cover Problem
DTSTART:20160511T111500
DTEND:20160511T121500
DTSTAMP:20261005T200140Z
UID:06a460d86d77a3aff7420dd8baa52ff4ba30f9f1f28fdb40e77e2182
CATEGORIES:Conferences - Seminars
DESCRIPTION:Sanjeev Khanna \nIn the set cover problem\, we are given a col
 lection of m subsets over a universe of n elements\, and the goal is to fi
 nd a sub-collection of sets whose union covers the universe. The set cover
  problem is a fundamental optimization problem with many applications in c
 omputer science and related disciplines. In this talk\, we investigate the
  set cover problem in the streaming model of computation whereby the sets 
 are presented one by one in a stream\, and the goal is to solve the set co
 ver problem using a space-efficient algorithm.  We show that to compute a
 n \\alpha-approximate set cover (for any \\alpha= o(\\sqrt{n})) via a sing
 le-pass streaming algorithm\, \\Theta(mn/\\alpha) space is both necessary 
 and sufficient (up to an O(\\log{n}) factor). We further study the problem
  of estimating the size of a minimum set cover (as opposed to finding the 
 actual sets)\, and show that this turns out to be a distinctly easier prob
 lem. Specifically\, we prove that \\Theta(mn/\\alpha^2) space is both suff
 icient and necessary (up to logarithmic factors) for estimating the size o
 f a minimum set cover to within a factor of \\alpha. Our algorithm in fact
  works for the more general problem of estimating the optimal value of a c
 overing integer program. These results provide a tight resolution of the s
 pace-approximation tradeoff for single-pass streaming algorithms for the s
 et cover problem. This is based on a joint work with Sepehr Assadi (Penn) 
 and Yang Li (Penn).  \nBio: Sanjeev Khanna is a Henry Salvatori Professor
  of Computer and Information Science at University of Pennsylvania. He rec
 eived a Ph.D. in Computer Science from Stanford University in 1996. His do
 ctoral work at Stanford received the 1996 Arthur Samuel prize for the best
  PhD dissertation in the Computer Science Department. He joined University
  of Pennsylvania in 1999 after spending three years as a researcher at Bel
 l Laboratories. Sanjeev’s primary research interests are in approximatio
 n algorithms\, combinatorial optimization\, and sublinear algorithms. He i
 s a Guggenheim Fellow and a Sloan Fellow. 
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR