Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 16, 2017, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Manuela Fischer
We present improved deterministic distributed algorithms for a number of well-studied matching problems. The common denominator of these results is a deterministic distributed rounding method for certain linear programs.
A sampling of our end results is as follows.
-- An O(log^2 Delta log (1/eps)+log^*n)-round deterministic distributed algorithm for a (2+eps)-approximate maximum matching in any n-node graph with maximum degree Delta. This is exponentially faster than the classic O(Delta+log^*n)-round 2-approximation of Panconesi and Rizzi [DIST'01].
-- An O(log^2 Delta log n)-round deterministic distributed algorithm for computing a maximal matching. This is the first improvement in about 20 years over the celebrated O(log^4 n)-round algorithm of Hanckowiak, Karonski, and Panconesi [SODA'98, PODC'99].
-- Extensions to weighted matching, (weighted) b-matching, and approximate minimum edge dominating set.
This is joint work with Mohsen Ghaffari.
Automatic MiSe System Software Version 1.4803M | admin login