« Deterministic (1+ε)-Approximate Maximum Matching with 𝗉𝗈𝗅𝗒(1/ε) Passes in the Semi-Streaming Model and Beyond
Deterministic (1+ε)-Approximate Maximum Matching with 𝗉𝗈𝗅𝗒(1/ε) Passes in the Semi-Streaming Model and Beyond
April 13, 2022, 11:00 AM - 12:00 PM
Location:
Online Event
Slobodan Mitrovic, University of California, Davis
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.
Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.