Improved deterministic distributed matching via rounding

DOI10.1007/S00446-018-0344-4MaRDI QIDQ2189173zbMATH OpenOpenAlexWikidataFDO

Authors Manuela Fischer

Publication date 15 June 2020

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.00900, https://drops.dagstuhl.de/opus/volltexte/2017/8002/

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)

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}^{\ast }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.

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

Cites work

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

Cited in

(14)

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

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)