The Taub Faculty of Computer Science Events and Talks
David Wajc (Google Research → Technion)
Tuesday, 22.11.2022, 14:30
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.