---
abstract: 'We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching ${\cal M}$ whose weight is at least $\frac{1}{8} M^{*}$ where $M^{*}$ 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.'
author:
- |
    Abhash Anand\
    Department of CSE,\
    I.I.T. Kanpur, India\
    [`abhash@cse.iitk.ac.in`]{}
- |
    Surender Baswana\
    Department of CSE,\
    I.I.T. Kanpur, India\
    [`sbaswana@cse.iitk.ac.in`]{}[^1]
- |
    Manoj Gupta\
    Department of CSE,\
    I.I.T. Delhi, India\
    [`gmanoj@cse.iitd.ernet.in`]{}
- |
    Sandeep Sen\
    Department of CSE,\
    I.I.T. Delhi, India\
    [`ssen@cse.iitd.ernet.in`]{}
bibliography:
- 'references.bib'
title: Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs
---

[^1]: Research supported by the Indo-German Max Planck Center for Computer Science (IMPECS).
