Title: Fractional Set Cover in the Streaming Model

Speaker: Ali Vakilian, PhD Candidate, MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) at the Massachusetts Institute of Technology

Location: Northeastern University, 440 Huntington Avenue, West Village H, 3rd Floor, Room #366, Boston, Massachusetts 02115

Abstract

Ali Vakilian studies the Fractional Set Cover problem in the streaming model.  That is, he considers the relaxation of the set cover problem over a universe of n elements and a collection of m sets, where each set can be picked fractionally, with a value in [0, 1].

Vakilian will present a randomized (1+ \eps)-approximation algorithm that makes p passes over the data, and uses O(polylog (m, n, 1/\eps)(mn^(O (1/(p \eps)))+ n)) memory space.  The algorithm works in both the set arrival and the edge arrival models.  To the best of his knowledge, this is the first streaming result for the fractional set cover problem.  He obtained his results by employing the multiplicative weights update framework in the streaming settings.

About the Speaker

Ali Vakilian is a second year PhD student in theory group, CSAIL at MIT and he is fortunate to have Erik Demaine as his advisor.  Vakilian received his master's degree in Computer Science from the University of Illinois at Urbana-Champaign (UIUC) in 2013.  During his master's studies at UIUC, he worked on combinatorial optimization and approximation algorithm design with Chandra Chekuri.  He received his bachelor's degree in Computer Engineering from Sharif University of Technology in 2011.

**** Please note that lunch will be served at 12:00 PM.  The talk will begin promptly at 12:30 PM. ****