Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

Abstract

We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching $\mathcal{M}$ whose weight is at least $1/8M^{\ast }$ where $M^{\ast }$ is the weight of the maximum weight matching. The algorithm achieves an expected amortized $O(\log n\log \mathcal{C})$ time per edge insertion or deletion, where $\mathcal{C}$ is the ratio of the weights of the highest weight edge to the smallest weight edge in the given graph. Using a simple randomized scaling technique, we are able to obtain a matching whith expected approximation ratio 4.9108.

References in corpus (3)

• Scaling algorithms for approximate and exact maximum weight matching
• Improved Bounds for Online Preemptive Matching
• Fully dynamic maximal matching in O(log n) update time