(1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings

DOI10.1145/3583668.3594570arXiv2212.14425WikidataQ130837168 ScholiaQ130837168MaRDI QIDQ6202220FDOQ6202220

Authors: Shang-En Huang, Hsin-Hao Su 

Publication date: 26 March 2024

Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: The maximum weighted matching (MWM) problem is one of the most well-studied combinatorial optimization problems in distributed graph algorithms. Despite a long development on the problem, and the recent progress of Fischer, Mitrovic, and Uitto [FMU22] who gave a $extpoly(1/epsilon,logn)$-round algorithm for obtaining a $(1-epsilon)$-approximate solution for unweighted maximum matching, it had been an open problem whether a $(1-epsilon)$-approximate MWM can be obtained in $extpoly(1/epsilon,logn)$ rounds in the CONGEST model. Algorithms with such running times were only known for special graph classes such as bipartite graphs [AKO18] and minor-free graphs [CS22]. For general graphs, the previously known algorithms require exponential in $(1/epsilon)$ rounds for obtaining a $(1-epsilon)$-approximate solution [FFK21] or achieve an approximation factor of at most 2/3 [AKO18]. In this work, we settle this open problem by giving a deterministic $extpoly(1/epsilon,logn)$-round algorithm for computing a $(1-epsilon)$-approximate MWM for general graphs in the CONGEST model. Our proposed solution extends the algorithm of Fischer, Mitrovic, and Uitto [FMU22], blends in the sequential algorithm from Duan and Pettie [DP14] and the work of Faour, Fuchs, and Kuhn [FFK21]. Interestingly, this solution also implies a CREW PRAM algorithm with $extpoly(1/epsilon,logn)$ span using only $O(m)$ processors. In addition, with the reduction from Gupta and Peng [GP13], we further obtain a semi-streaming algorithm with $extpoly(1/epsilon)$ passes. When $epsilon$ is smaller than a constant $o(1)$ but at least $1/lo{g}^{o(1)}n$, our algorithm is more efficient than both Ahn and Guha's $extpoly(1/epsilon,logn)$-passes algorithm [AG13] and Gamlath, Kale, Mitrovic, and Svensson's $(1/epsilon{)}^{O(1/epsilo{n}^2)}$-passes algorithm [GKMS19].

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

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Distributed minimum cut approximation
• Faster scaling algorithms for general graph matching problems
• Distributed verification and hardness of distributed approximation
• Maximum matching and a polyhedron with 0,1-vertices
• Linear-time approximation for maximum weight matching
• A simple approximation algorithm for the weighted matching problem
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Title not available (Why is that?)
• A fast and simple randomized parallel algorithm for maximal matching
• Local computation: lower and upper bounds
• On the distributed complexity of computing maximal matchings
• Improved Distributed Approximate Matching
• Sublinear-Time Parallel Algorithms for Matching and Related Problems
• Distributed approximate matching
• Distributed Weighted Matching
• Approximating weighted matchings in parallel
• Connectivity oracles for failure prone graphs
• Distributed approximation of maximum independent set and maximum matching
• Weighted Matchings via Unweighted Augmentations
• Deterministic distributed edge-coloring with fewer colors
• Linear programming in the semi-streaming model with application to the maximum matching problem
• Distributed approximate maximum matching in the CONGEST model

This page was built for publication: (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings

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