ARC Colloquium: David Wajc (Stanford)

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.

---------------------------------------------------------------

Speaker’s Webpage

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

Event Details

Date/Time:

  • Monday, October 24, 2022
    11:00 am - 12:00 pm
Location: Klaus 1116