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

Jiale Chen

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 maint…