Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

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\mathrm{/}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.