Slobodan Mitrovic: MapReduce and approximate Maximal Matchings
Friday, October 6, 2017 - 1:00pm to 2:30pm
Location:
32-G531
Speaker:
Slobodan Mitrovic
Biography:
MIT
Seminar group:
The last decade has witnessed the success of a number of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. These frameworks allow for much more local memory and computation, compared to the classical distributed or PRAM models. In the context of these frameworks, we will discuss algorithms for computing a constant factor approximation of Maximal Matching.
We will start by presenting a Maximal Matching PRAM algorithm by Israeli and Itai '86, which requires O(log |V|) communication rounds in the MPC framework. Next we will discuss the work of Lattanzi et al. '11, that shows how to improve upon O(log |V|) communication rounds when the memory per machine is superlinear in |V|. Finally, we will see an algorithm that achieves O((log log |V|)^2) rounds even when the memory per machine is slightly sublinear in |V|.