  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 $\text{poly}(1/\epsilon, \log n)$-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 $\text{poly}(1/\epsilon, \log n)$ 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
$\text{poly}(1/\epsilon, \log n)$-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 $\text{poly}(1/\epsilon, \log n)$ span using
only $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 than
both 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].
