Authors:
Sepehr Assadi, MohammadHossein Bateni, Vahab Mirrokni
Abstract:
Maximum weight matching is one of the most fundamental combinatorial optimization problems
with a wide range of applications in data mining and bioinformatics. Developing distributed
weighted matching algorithms is challenging due
to the sequential nature of efficient algorithms for
this problem. In this paper, we develop a simple
distributed algorithm for the problem on general
graphs with approximation guarantee of 2 + that
(nearly) matches that of the sequential greedy algorithm. A key advantage of this algorithm is that
it can be easily implemented in only two rounds
of computation in modern parallel computation
frameworks such as MapReduce. We also demonstrate the efficiency of our algorithm in practice on
various graphs (some with half a trillion edges) by
achieving objective values always close to what
is achievable in the centralized setting.
Conference version:
[PDF]
Presentation slides:
[PDF] (MohammadHossein's @ICML)