Random Proposals: A Softmax-Based Local-Improvement Framework for Maximum Weighted Matching

We propose a randomized local-improvement algorithm for the Maximum Weighted Matching (MWM) problem. Our method introduces a softmax-based biased sampling mechanism that achieves local $\epsilon$-dominance and yields an expected $\frac{1}{2}-\epsilon$ approximation ratio. We prove convergence guarantees and show that the algorithm runs in $O\text{\hspace{0.17em}⁣}(m\log (1\mathrm{/}\epsilon )\mathrm{/}{p}_{\min })$ time, where $p_{\min }$ is the minimum softmax proposal probability over all edges; under mild conditions on the bias parameter and weight range, this simplifies to $O(m\log (1\mathrm{/}\epsilon ))$. The framework provides a tunable tradeoff between convergence speed and approximation quality.