License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.17
URN: urn:nbn:de:0030-drops-80027
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8002/
Go to the corresponding LIPIcs Volume Portal

Fischer, Manuela

Improved Deterministic Distributed Matching via Rounding

pdf-format:
LIPIcs-DISC-2017-17.pdf (0.5 MB)

Abstract

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 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(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 2-approximation of Panconesi and Rizzi [DIST'01]. With some modifications, the algorithm can also find an epsilon-maximal matching which leaves only an epsilon-fraction 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 b-matching. 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 query-complexity 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:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8002},
  URN =		{urn:nbn:de:0030-drops-80027},
  doi =		{10.4230/LIPIcs.DISC.2017.17},
  annote =	{Keywords: distributed graph algorithms, deterministic distributed algorithms, rounding linear programs, maximal matching, maximum matching approximation}
}

Keywords: distributed graph algorithms, deterministic distributed algorithms, rounding linear programs, maximal matching, maximum matching approximation
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI