Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum vertex cover, for any n-vertex graph and any constant epsilon > 0. These improve the state of the art as follows: Our MIS algorithm leads to a simple O(log log A)-round MIS algorithm in the CONGESTED-CLIQUE model of distributed computing, which improves on the (O) over tilde(root log Delta)-round algorithm of Ghaffari [PODC'17]. Our O(log log(2) n)-round (1 + epsilon)-approximate maximum matching algorithm simplifies or improves on the following prior work: O(log2 log n)-round (1 + epsilon)-approximation algorithm of Czumaj et al. [STOC'18] and O(log log n)-round (1 + epsilon) approximation algorithm of Assadi et al. [arXiv'17]. Our O(log log n)-round (2 + epsilon)-approximate minimum vertex cover algorithm improves on an O(log log n)-round O(1)-approximation of Assadi et al. [arXiv'17].
Slobodan Mitrovic, Mohsen Ghaffari