*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
David Wajc (Stanford)
October 24, 2022
Klaus 1116 - 11:00 am
Title: Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
Abstract: In this work, we present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2. Specifically, we obtain a 1+1/√2+ϵ≈1.707+ϵ approximation in bipartite graphs and a 1.973+ϵ approximation in general graphs. We thus answer in the affirmative the major open question first posed in the influential work of Onak and Rubinfeld (STOC'10) and repeatedly asked in the dynamic graph algorithms literature.
Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS'21) to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier. The obtained randomized algorithms work against an adaptive adversary and guarantee worst-case polylog update time, both w.h.p. In the talk I will focus on the high-level ideas sufficient to achieve some (unspecified) better-than-two approximation against an oblivious adversary, in expectation, in amortized polylog time.
---------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836 and http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
