Distributed local approximation algorithms for maximum matching in graphs and hypergraphs

DOI10.1137/19M1279241MaRDI QIDQ5115699zbMATH OpenFDO

Authors David G. Harris

Publication date 18 August 2020

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

matchingderandomizationhypergraphedge coloringLOCALNash-Williams decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in a hypergraph of rank $r$. Our main result is a deterministic algorithm to generate a matching which is an $O(r)$-approximation to the maximum weight matching, running in $ildeO(rlogDelta+lo{g}^{2}Delta+lo{g}^{\ast }n)$ rounds. (Here, the $ildeO()$ notations hides $extpolyloglogDelta$ and $extpolylogr$ factors). This is based on a number of new derandomization techniques extending methods of Ghaffari, Harris & Kuhn (2017). As a main application, we obtain nearly-optimal algorithms for the long-studied problem of maximum-weight graph matching. Specifically, we get a $(1+epsilon)$ approximation algorithm using $ildeO(logDelta/epsilo{n}^3+extpolylog(1/epsilon,loglogn))$ randomized time and $ildeO(lo{g}^{2}Delta/epsilo{n}^4+lo{g}^{\ast }n/epsilon)$ deterministic time. The second application is a faster algorithm for hypergraph maximal matching, a versatile subroutine introduced in Ghaffari et al. (2017) for a variety of local graph algorithms. This gives an algorithm for $(2Delta-1)$-edge-list coloring in $ildeO(lo{g}^{2}Deltalogn)$ rounds deterministically or $ildeO((loglogn{)}^3)$ rounds randomly. Another consequence (with additional optimizations) is an algorithm which generates an edge-orientation with out-degree at most $lceil(1+epsilon)lambdaceil$ for a graph of arboricity $lambda$; for fixed $epsilon$ this runs in $ildeO(lo{g}^{6}n)$ rounds deterministically or $ildeO(lo{g}^{3}n)$ rounds randomly.

Recommendations

• Improved deterministic distributed matching via rounding
• Improved deterministic distributed matching via rounding
• Distributed approximate matching
• Distributed approximate maximum matching in the CONGEST model
• Distributed approximate matching

Cites work

• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• Adapting local sequential algorithms to the distributed setting
• An Improved Distributed Algorithm for Maximal Independent Set
• Approximating weighted matchings in parallel
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Concentration and moment inequalities for polynomials of independent random variables
• Decomposition of Graphs Into Closed and Endless Chains
• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• Deterministic distributed edge-coloring with fewer colors
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Distributed Computing: A Locality-Sensitive Approach
• Distributed approximate matching
• Distributed approximate maximum matching in the CONGEST model
• Distributed approximation of maximum independent set and maximum matching
• Distributed degree splitting, edge coloring, and orientations
• Improved Distributed Approximate Matching
• Improved deterministic distributed matching via rounding
• Locality in Distributed Graph Algorithms
• Some simple distributed algorithms for sparse networks
• The locality of distributed symmetry breaking
• The price of being near-sighted

Cited in

(11)

• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
• On the distributed complexity of the semi-matching problem
• Distributed maximum maintenance on hierarchically divided graphs
• Best of two local models: centralized local and distributed local algorithms
• A Local Computation Approximation Scheme to Maximum Matching
• Distributed coloring of hypergraphs
• Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs
• Distributed approximation of maximum independent set and maximum matching
• Improved deterministic distributed matching via rounding
• Distributed Algorithm for Better Approximation of the Maximum Matching

This page was built for publication: Distributed local approximation algorithms for maximum matching in graphs and hypergraphs

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