Themistoklis will start as a postdoc with us in March. He's using the opportunity of travelling to PODC for a brief visit. If you're interested, please don't hesitate to have a chat!

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

I will present O(log log 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(log log ∆)-round MIS algorithm in the CONGESTED-CLIQUE model of distributed computing. This result improves exponentially on the algorithm of Ghaffari [PODC’17] requiring O~(p log ∆)-rounds.
• Our O(log log n)-round (1 + ε)-approximate maximum matching algorithm simplifies or improves on the following prior work: O(log^2 log n)-round (1 + ε)-approximation algorithm of Czumaj et al. [STOC’18] and O(log log n)-round (1 + ε)- approximation algorithm of Assadi et al. [arXiv’17].
• Our O(log log n)-round (2 + ε)-approximate minimum vertex cover algorithm improves on an O(log log n)-round O(1)-approximation of Assadi et al. [arXiv’17].

Christoph Lenzen

--email hidden

passcode not visible

logged in users only