Seminar Details
Deterministic (1+ε)-Approximate Maximum Matching with ð—‰ð—ˆð—…ð—’(1/ε) Passes in the Semi-Streaming Model and Beyond
- Start Date: April 13, 2022
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Slobodan Mitrovic - University of California, Davis
- Event Location: Online Event
- Event Additional Info: <p>Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar" target="_blank">https://theory.cs.rutgers.edu/theory_seminar</a> </p>
- Presentation Type: Stand Alone Presentation
- Abstract:
In this talk, I will present a recent result on computing (1+ε)-approximate maximum matchings. I will outline a deterministic approach that solves this problem in poly(1/ε) semi-streaming passes. This algorithm exponentially improves on the well-known randomized exp(O(1/ε))-pass algorithm from the seminal work by McGregor'05 and the recent deterministic algorithm by Tirodkar'18. I will also briefly touch on how these ideas extend to other models of computation. In particular, they yield a poly(log n, 1/ε) round algorithm for computing (1+ε)-approximate maximum matchings in CONGEST. In terms of the dependence on 1/ε, this improves exponentially state-of-the-art result by Lotker, Patt-Shamir, and Pettie'15.
This is a joint work with Manuela Fischer and Jara Uitto.