We present improved deterministic distributed algorithms for a number of well-studied 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 · log n -round deterministic distributed algorithm for computing a maximal matching, in n-node graphs with maximum degree . This is the first improvement in about 20 years over the celebrated O(log 4 n)-round algorithm of Hańćkowiak, Karoński, and Panconesi [SODA'98, PODC'99]. • A deterministic distributed algorithm for computing a (2 + ε)-approximation of maximum matching in O log 2 · log 1 ε + log * n rounds. This is exponentially faster than the classic O( + log * n)-round 2-approximation of Panconesi and Rizzi [DIST'01]. With some modifications, the algorithm can also find an almost maximal matching which leaves only an ε-fraction of the edges on unmatched nodes. • An O log 2 · log 1 ε · log 1+ε W + log * n -round deterministic distributed algorithm for computing a (2 + ε)-approximation of a maximum weighted matching, and also for the more general problem of maximum weighted b-matching. Here, W denotes the maximum normalized weight. These improve over the O log 4 n · log 1+ε W -round (6 + ε)-approximation algorithm of Panconesi and Sozio [DIST'10].
More recently, Fischer substantially improved this bound to O(log 2 ∆ log n) REF .
Improved deterministic distributed matching via rounding
Distributed Computing
Distributed Computing
Computer Science Engineering