The Power of Local Marginals: An $O({\epsilon }^{-1})$-Aspect-Ratio Reduction for Dynamic Weighted Matching

Abstract

We study dynamic maximum weight matching (MWM) under edge insertions and deletions in two settings: maintaining a $(1\pm \epsilon )$-approximation to the optimum weight, and maintaining an explicit $(1-\epsilon )$-approximate matching. Our main result is a reduction that transforms instances of polynomial aspect ratio into instances of aspect ratio $O({\epsilon }^{-1})$. The reduction applies to general graphs in both settings and is compatible with partially dynamic updates. The reduction is based on a structural property of local marginals. After grouping edges into weight classes, the global marginal contribution of one class relative to all lower classes is approximated by its marginal contribution within a local weight window of aspect ratio $O({\epsilon }^{-1})$. Summing these local marginals yields a value composition lemma that uses only approximate optimum values of the local windows. This improves the value reduction of Gupta and Peng (FOCS 2013), whose local aspect ratio is ${\epsilon }^{-\Theta ({\epsilon }^{-1})}$. The same structural property yields an improved matching composition lemma for explicit matchings, reducing the local aspect ratio of Bernstein--Chen--Dudeja--Langley--Sidford--Tu (SODA 2025) from $O({\epsilon }^{-2})$ to $O({\epsilon }^{-1})$.