# Improved Deterministic Distributed Matching via Rounding

arXiv: https://arxiv.org/abs/1703.00900 · HTML: https://mlsanity.com/paper/1703.00900/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2017.

## Built on by (most cited first, 1 of 1)

- [Multi-Domain Learning with Global Expert Mapping](https://mlsanity.com/paper/2604.18842/) (2026)

## Abstract (arXiv)

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(log2 Delta· log n)-round deterministic distributed algorithm for computing a maximal matching, in n-node graphs with maximum degree Delta. This is the first improvement in about 20 years over the celebrated O(log4 n)-round algorithm of Ha'n'ckowiak, Karo'nski, and Panconesi [SODA'98, PODC'99]. -- A deterministic distributed algorithm for computing a (2+varepsilon)-approximation of maximum matching in O(log2 Delta · log frac1varepsilon + log^ * n) rounds. This is exponentially faster than the classic O(Delta +log^* n)-round 2-approximation of Panconesi and Rizzi [DIST'01]. With some modifications, the algorithm can also find an varepsilon-maximal matching which leaves only an varepsilon-fraction of the edges on unmatched nodes. -- An O(log2 Delta · log frac1varepsilon + log^ * n)-round deterministic distributed algorithm for computing a (2+varepsilon)-approximation of a maximum weighted matching, and also for the more general problem of maximum weighted b-matching. These improve over the O(log4 n · log1+varepsilon W)-round (6+varepsilon)-approximation algorithm of Panconesi and Sozio [DIST'10], where W denotes the maximum normalized weight.