CS Seminar
Vahab Mirrokni, Google
“Randomized Composable Core-sets for Distributed Computation”
Hosted by Amin Karbasi
Abstract: An effective technique for solving optimization problems over massive data sets is to partition the data into smaller pieces, solve the problem on each piece and compute a representative solution from it, and finally obtain a solution inside the union of the representative solutions for all pieces. Such an algorithm can be implemented easily in 2 rounds of MapReduces or be applied in an streaming model. This technique can be captured via the concept of {\em composable core-sets}, and has been recently applied to solve diversity maximization problems as well as several clustering problems. However, for coverage and submodular maximization problems, impossibility bounds are known for this technique. In this talk, after a initial discussion about this technique and applications in diversity maximization and clustering problems, we focus on the submodular maximization problem, and show how to apply a randomized variant of composable core-set problem, and achieve 1/3-approximation for monotone and non-montone submodualr maximization problems. We prove this result by applying a simple greedy algorithm and show that a large class of algorithms can be deployed in this framework. Time-permitting, we show a more complicated algorithm that achieves 54% of the optimum in two rounds of MapReduces.
The main part of the talk is to appear in STOC 2015 and is a joint work with Morteza ZadiMoghaddam. The initial parts are from two recent papers that appeared in PODS 2014 and NIPS 2014.
Bio: Vahab Mirrokni is a senior staff research scientist at at Google Research NYC, where he is heading the algorithms research group. He joined Google after holding research positions at Microsoft Research, MIT and Amazon. He received his PhD from MIT in 2005 and his B.Sc. from Sharif University in 2001. Vahab’s research interests include large-scale graph mining, approximation algorithms, and algorithmic game theory. At Google, he is mainly working on algorithmic and economic problems related to the internet search and online advertising. As two of his recent projects, he is serving a tech lead manager for the large-scale graph mining, and market algorithms teams based in Google Research NYC.