Improved deterministic distributed matching via rounding

DOI10.1007/S00446-018-0344-4zbMATH Open1445.68335arXiv1703.00900OpenAlexW2748046883WikidataQ129148605 ScholiaQ129148605MaRDI QIDQ2189173FDOQ2189173

Authors: Manuela Fischer 

Publication date: 15 June 2020

Published in: Distributed Computing (Search for Journal in Brave)

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(lo{g}^{2}Deltacdotlogn)$-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(lo{g}^{4}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(lo{g}^{2}Deltacdotlogfrac1varepsilon+lo{g}^{\ast }n)$ rounds. This is exponentially faster than the classic $O(Delta+lo{g}^{*}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(lo{g}^{2}Deltacdotlogfrac1varepsilon+lo{g}^{\ast }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(lo{g}^{4}ncdotlo{g}_{1+varepsilon}W)$-round $(6+varepsilon)$-approximation algorithm of Panconesi and Sozio [DIST'10], where $W$ denotes the maximum normalized weight.

Full work available at URL: https://arxiv.org/abs/1703.00900

Recommendations

• Improved deterministic distributed matching via rounding
• Improved Distributed Approximate Matching
• Distributed near-optimal matching
• Distributed near-optimal matching
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Distributed algorithm for approximating the maximum matching
• Improved approximation algorithms for stochastic matching
• Distributed approximate matching
• Distributed approximate matching
• Algorithms – ESA 2004

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)

Cites Work

• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Locality in Distributed Graph Algorithms
• What cannot be computed locally!
• Edge Dominating Sets in Graphs
• An improved parallel algorithm for maximal matching
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• A fast and simple randomized parallel algorithm for maximal matching
• On the distributed complexity of computing maximal matchings
• Distributed algorithm for approximating the maximum matching
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Improved Distributed Approximate Matching
• Title not available (Why is that?)
• The locality of distributed symmetry breaking
• Some simple distributed algorithms for sparse networks
• Distributed algorithms for \textsc{Edge Dominating Sets}
• Distributed approximate matching
• Distributed Weighted Matching
• Algorithms – ESA 2004
• Distributed algorithms for covering, packing and maximum weighted matching
• Distributed Algorithm for Better Approximation of the Maximum Matching
• An Improved Distributed Algorithm for Maximal Independent Set
• Distributed maximal matching, greedy is optimal
• Julius Petersen's theory of regular graphs
• Linear-in-delta lower bounds in the LOCAL model
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• A faster distributed algorithm for computing maximal matchings deterministically
• Distributed degree splitting, edge coloring, and orientations
• On the complexity of local distributed graph problems
• Toward more localized local algorithms: removing assumptions concerning global knowledge

Cited In (14)

• Distributed half-integral matching and beyond
• Distributed half-integral matching and beyond
• Distributed near-optimal matching
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Faster deterministic distributed MIS and approximate matching
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Distributed maximal matching, greedy is optimal
• Improved deterministic distributed matching via rounding
• Node and edge averaged complexities of local graph problems
• Distributed dense subgraph detection and low outdegree orientation
• The Match-Maker: Constant-Space Distributed Majority via Random Walks
• Distributed approximate maximum matching in the CONGEST model
• Improved Distributed Approximate Matching
• Distributed backup placement

This page was built for publication: Improved deterministic distributed matching via rounding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189173)