Speaker: Ali Vakilian,
PhD student,
Department of Computer Science,
Massachusetts Institute of Technology (MIT)
Title: Algorithm for Big Data (Streaming Algorithm for The Set Cover Problem)
Local Organizer: Dr. Ghodsi
Time: Tuesday, Jan. 13, 3:00-4:00 PM
Location: Computer Engineering Department, Sharif University of Technology
Abstract:
I will begin the talk with a brief introduction to Big Data and its algorithmic challenges and opportunities. Next, I will focus on streaming algorithms and in particular designing efficient streaming algorithms for the Set Cover problem. In a recent work with Erik Demaine, Piotr Indyk and Sepideh Mahabadi, We developed the first streaming algorithm and the ?first two-party communication protocol that
uses a constant number of passes/rounds and sublinear space/communication for logarithmic approximation
to the classic Set Cover problem. Specially, for n elements and m sets, our algorithm/
protocol achieves a space bound of O(m \cdot n^\delta log^2 n \log m) (for any \delta > 0) using O(4^(1/\delta))
passes/rounds while achieving an approximation factor of O(4^(1/\delta) log n) in polynomial time. If we
allow the algorithm/protocol to spend exponential time per pass/round, we achieve an approximation
factor of O(4^(1/\delta)). Our approach uses randomization, which we show is necessary: no deterministic
constant approximation is possible (even given exponential time) using o(mn) space. These results
are some of the first on streaming algorithms and efficient two-party communication protocols for
approximation algorithms.
At the end, I will mention some recent follow-up results of this work.