(1-eps)-Approximate Maximum Weighted Matching in poly(1/eps, log n) Time in the Distributed and Parallel Settings
(1-eps)-Approximate Maximum Weighted Matching in poly(1/eps, log n) Time in the Distributed and Parallel Settings
复制标题
(1-eps)-分布式和并行设置中 Poly(1/eps, log n) 时间的近似最大加权匹配
DOI：
10.1145/3583668.3594570
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Su, Hsin-Hao
中科院分区：
文献类型：
--
作者：
Huang, Shang-En;Su, Hsin-Hao
最大加权匹配问题是分布式图算法中研究最多的组合优化问题之一。尽管对这个问题进行了很长时间的研究，最近Fischer，Mitrovic和Uitto[16]给出了一种Poly(1/ϵ，Logn)轮次算法来获得未加权最大匹配的(1−ϵ)-近似解，但在拥塞模型中Poly(1/−ϵ，Logn)轮次能否获得(1ϵ)-近似MWM一直是一个悬而未决的问题。具有这种运行时间的算法仅为特殊的图类所知，例如二部图[1]和无副图[8]。对于一般的图，已知的算法需要在(1/ϵ)轮中指数运算才能获得(1−ϵ)-近似解[13]或获得至多2/3的逼近因子[1]。在这项工作中，我们通过给出一个确定的Poly(1/ϵ，logn)轮算法来解决这一公开问题，该算法用于计算拥塞模型中一般图的(1−ϵ)-近似最大加权平均。我们提出的解决方案扩展了Fischer，Mitrovic和Uitto的算法[16]，融合了Duan和Pettie[11]的顺序算法以及Faour，Fuchs和Kuhn的工作[13]。有趣的是，该解决方案还包括仅使用O(M)处理器的具有Poly(1/ϵ，logn)跨度的Crew PRAM算法，以及在半流模型中的Poly(1/ϵ)-Pass算法。
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/ϵ, logn)-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/ϵ, logn) 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/ϵ, logn)-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/ϵ, logn) span using onlyO(m) processors, and a poly(1/ϵ)-passes algorithm in the semi-streaming model.