Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

CS Colloquia: Dynamic Matching with Better-than-2 Approx in Polylog Update Time
event speaker icon
David Wajc (Google Research → Technion)
event date icon
Tuesday, 22.11.2022, 14:30
event location icon
Room 337 Taub Bld.
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. This answers in the affirmative the value version of a major open question, repeatedly asked in the dynamic graph algorithms literature. Based on an upcoming SODA 2023 best paper, joint with Sayan Bhattacharya, Peter Kiss and Thatchaphol Saranurak.