On the Single-Pass Streaming Complexity of the Set Cover Problem
Event details
| Date | 11.05.2016 |
| Hour | 11:15 › 12:15 |
| Speaker | Sanjeev Khanna |
| Location | |
| Category | Conferences - Seminars |
In the set cover problem, we are given a collection of m subsets over a universe of n elements, and the goal is to find a sub-collection of sets whose union covers the universe. The set cover problem is a fundamental optimization problem with many applications in computer 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 cover problem using a space-efficient algorithm. We show that to compute an \alpha-approximate set cover (for any \alpha= o(\sqrt{n})) via a single-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 problem. Specifically, we prove that \Theta(mn/\alpha^2) space is both sufficient and necessary (up to logarithmic factors) for estimating the size of 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 covering integer program. These results provide a tight resolution of the space-approximation tradeoff for single-pass streaming algorithms for the set cover problem. This is based on a joint work with Sepehr Assadi (Penn) and Yang Li (Penn).
Bio: Sanjeev Khanna is a Henry Salvatori Professor of Computer and Information Science at University of Pennsylvania. He received a Ph.D. in Computer Science from Stanford University in 1996. His doctoral 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 Bell Laboratories. Sanjeev’s primary research interests are in approximation algorithms, combinatorial optimization, and sublinear algorithms. He is a Guggenheim Fellow and a Sloan Fellow.
Bio: Sanjeev Khanna is a Henry Salvatori Professor of Computer and Information Science at University of Pennsylvania. He received a Ph.D. in Computer Science from Stanford University in 1996. His doctoral 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 Bell Laboratories. Sanjeev’s primary research interests are in approximation algorithms, combinatorial optimization, and sublinear algorithms. He is a Guggenheim Fellow and a Sloan Fellow.
Practical information
- Informed public
- Free
- This event is internal
Organizer
- Michael Kapralov
Contact
- Pauline Raffestin