English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The maximum weighted matching (MWM) problem is one of the most well-studiedcombinatorial optimization problems in distributed graph algorithms. Despite along development on the problem, and the recent progress of Fischer, Mitrovic,and Uitto [FMU22] who gave a $\text{poly}(1/\epsilon, \log n)$-round algorithmfor obtaining a $(1-\epsilon)$-approximate solution for unweighted maximummatching, it had been an open problem whether a $(1-\epsilon)$-approximate MWMcan be obtained in $\text{poly}(1/\epsilon, \log n)$ rounds in the CONGESTmodel. Algorithms with such running times were only known for special graphclasses such as bipartite graphs [AKO18] and minor-free graphs [CS22]. Forgeneral 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 thiswork, we settle this open problem by giving a deterministic$\text{poly}(1/\epsilon, \log n)$-round algorithm for computing a$(1-\epsilon)$-approximate MWM for general graphs in the CONGEST model. Ourproposed solution extends the algorithm of Fischer, Mitrovic, and Uitto[FMU22], blends in the sequential algorithm from Duan and Pettie [DP14] and thework of Faour, Fuchs, and Kuhn [FFK21]. Interestingly, this solution alsoimplies a CREW PRAM algorithm with $\text{poly}(1/\epsilon, \log n)$ span usingonly $O(m)$ processors. In addition, with the reduction from Gupta and Peng[GP13], we further obtain a semi-streaming algorithm with$\text{poly}(1/\epsilon)$ passes. When $\epsilon$ is smaller than a constant$o(1)$ but at least $1/\log^{o(1)} n$, our algorithm is more efficient thanboth Ahn and Guha's $\text{poly}(1/\epsilon, \log n)$-passes algorithm [AG13]and Gamlath, Kale, Mitrovic, and Svensson's$(1/\epsilon)^{O(1/\epsilon^2)}$-passes algorithm [GKMS19].

$(1-\epsilon)$-Approximate Maximum Weighted Matching in Distributed, Parallel, and Semi-Streaming Settings