Fully Dynamic $(1+\epsilon)$-Approximate Matchings

Understand

We present the first data structures that maintain near optimal maximum cardinality and maximum weighted matchings on sparse graphs in sublinear time per update.

• Our main result is a data structure that maintains a $(1+\epsilon)$ approximation of maximum matching under edge insertions/deletions in worst case $O(\sqrt{m}\epsilon^{-2})$ time per update.
• This improves the 3/2 approximation given in [Neiman,Solomon,STOC 2013] which runs in similar time.
• The result is based on two ideas.