Fischer, Manuela
Improved Deterministic Distributed Matching via Rounding
Abstract
We present improved deterministic distributed algorithms for a number of wellstudied matching problems, which are simpler, faster, more accurate, and/or more general than their known counterparts. The common denominator of these results is a deterministic distributed rounding method for certain linear programs, which is the first such rounding method, to our knowledge.
A sampling of our end results is as follows.
 An O(log^2 Delta log n)round deterministic distributed algorithm for computing a maximal matching, in nnode graphs with maximum degree Delta. 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].
 A deterministic distributed algorithm for computing a (2+epsilon)approximation of maximum matching in O(log^2 Delta log(1/epsilon) + log^* n) rounds. This is exponentially faster than the classic O(Delta + log^* n)round 2approximation of Panconesi and Rizzi [DIST'01]. With some modifications, the algorithm can also find an epsilonmaximal matching which leaves only an epsilonfraction of the edges on unmatched nodes.
 An O(log^2 Delta log(1/epsilon) + log^* n)round deterministic distributed algorithm for computing a (2+epsilon)approximation of a maximum weighted matching, and also for the more general problem of maximum weighted bmatching. These improve over the O(log^4 n log_(1+epsilon) W)round (6+epsilon)approximation algorithm of Panconesi and Sozio [DIST'10], where W denotes the maximum normalized weight.
 A deterministic local computation algorithm for a (2+epsilon)approximation of maximum matching with 2^O(log^2 Delta) log^* n queries. This improves almost exponentially over the previous deterministic constant approximations which have querycomplexity of 2^Omega(Delta log Delta) log^* n.
BibTeX  Entry
@InProceedings{fischer:LIPIcs:2017:8002,
author = {Manuela Fischer},
title = {{Improved Deterministic Distributed Matching via Rounding}},
booktitle = {31st International Symposium on Distributed Computing (DISC 2017)},
pages = {17:117:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770538},
ISSN = {18688969},
year = {2017},
volume = {91},
editor = {Andr{\'e}a W. Richa},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8002},
URN = {urn:nbn:de:0030drops80027},
doi = {10.4230/LIPIcs.DISC.2017.17},
annote = {Keywords: distributed graph algorithms, deterministic distributed algorithms, rounding linear programs, maximal matching, maximum matching approximation}
}
2017
Keywords: 

distributed graph algorithms, deterministic distributed algorithms, rounding linear programs, maximal matching, maximum matching approximation 
Seminar: 

31st International Symposium on Distributed Computing (DISC 2017)

Issue date: 

2017 
Date of publication: 

2017 