Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
Speaker:Themistoklis Gouleakis
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio: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!
Event Type:AG1 Mittagsseminar (others' work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Friday, 20 July 2018
Duration:30 Minutes
Building:E1 5 (SWS)
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].

Name(s):Christoph Lenzen
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Christoph Lenzen, 07/19/2018 06:53 PM
Last modified:
Uwe Brahm/MPII/DE, 07/20/2018 04:01 AM
  • Christoph Lenzen, 07/19/2018 06:53 PM -- Created document.