2018/02/22 by Ghaffari, Mohsen, Gouleakis, Themis, Konrad, Christian +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1802.08237
We present O(loglog n)-round algorithms in the Massively Parallel Computation (MPC) model, with O(n) memory per machine, that compute a maximal independent set, a 1+ε approximation of maximum matching, and a 2+ε approximation of minimum vertex cover, for any n-vertex graph and any constant ε>0. These improve the state of the art as follows: - Our MIS algorithm leads to a simple O(loglog Δ)-round MIS algorithm in the Congested Clique model of distributed computing, which improves on the O(√(log Δ))-round algorithm of Ghaffari [PODC'17]. - Our O(loglog n)-round (1+ε)-approximate maximum matching algorithm simplifies or improves on the following prior work: O(log2log n)-round (1+ε)-approximation algorithm of Czumaj et al. [STOC'18] and O(loglog n)-round (1+ε)-approximation algorithm of Assadi et al. [SODA'19]. - Our O(loglog n)-round (2+ε)-approximate minimum vertex cover algorithm improves on an O(loglog n)-round O(1)-approximation of Assadi et al. [arXiv'17].