(1-ϵ)-Approximate Maximum Weighted Matching in poly(1/ϵ, log n) Time in the Distributed and Parallel Settings
Part Of
Proceedings of the Annual ACM Symposium on Principles of Distributed Computi
Start Page
44
End Page
54
ISBN (of the container)
979-840070121-4
Date Issued
2023-06-16
Author(s)
Hsin-Hao Su
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 [16] who gave a poly(1/ϵ, log n)-round algorithm for obtaining a (1 − ϵ)-approximate solution for unweighted maximum matching, it had been an open problem whether a (1 − ϵ)-approximate mwm can be obtained in poly(1/ϵ, log n) rounds in the CONGEST model. Algorithms with such running times were only known for special graph classes such as bipartite graphs [1] and minor-free graphs [8]. For general graphs, the previously known algorithms require exponential in (1/ϵ) rounds for obtaining a (1 − ϵ)-approximate solution [13] or achieve an approximation factor of at most 2/3 [1]. In this work, we settle this open problem by giving a deterministic poly(1/ϵ, log n)-round algorithm for computing a (1 − ϵ)-approximate mwm for general graphs in the CONGEST model. Our proposed solution extends the algorithm of Fischer, Mitrovic, and Uitto [16], blends in the sequential algorithm from Duan and Pettie [11] and the work of Faour, Fuchs, and Kuhn [13]. Interestingly, this solution also implies a CREW PRAM algorithm with poly(1/ϵ, log n) span using only O(m) processors, and a poly(1/ϵ)-passes algorithm in the semi-streaming model.
Event(s)
42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2023
Publisher
ACM
Type
conference paper