Campus Event Calendar

Event Entry

What and Who

Fully Dynamic $(1+ε)$-Approximate Matchings

Manoj Gupta
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience

Date, Time and Location

Thursday, 29 August 2013
30 Minutes
E1 4


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. The first is to re-run a static algorithm after a chosen number of updates to ensure approximation guarantees. The second is to judiciously trim the graph to a smaller equivalent one whenever possible.

We also study extensions of our approach to the weighted setting, and combine it with known frameworks to obtain arbitrary approximation ratios. For a constant $\epsilon$ and for graphs with edge weights between 1 and N, we design an algorithm that maintains an $(1+\epsilon)$-approximate maximum weighted matching in $O(\sqrt{m} \log N)$ time per update. The only previous result for maintaining weighted matchings on dynamic graphs has an approximation ratio of 4.9108, and was shown in [Anand,Baswana,Gupta,Sen, FSTTCS 2012, arXiv 2012].


Anand Sankaran
--email hidden
passcode not visible
logged in users only

Anand Sankaran, 08/16/2013 10:41 -- Created document.