Seminar Details
Maintaining and Rounding Dynamic Fractional Matchings
- Start Date: April 28, 2021
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Sayan Bhattacharya - University of Warwick
- Event Location: Online Event
- Event Additional Info: <p>Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://sites.google.com/view/dimacs-theory-seminar/home" target="_blank">https://sites.google.com/view/dimacs-theory-seminar/home</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
Consider a dynamic graph G = (V, E) that is undergoing a sequence of edge insertions/deletions. We want to design an algorithm that maintains an (approximately) maximum matching in this dynamic graph G. The \`\`update time" of an algorithm refers to the time it takes to handle the insertion/deletion of an edge in G. We will like to ensure that our algorithm has small (polylogarithmic) update time.
This problem has received considerable attention in the past decade. In this talk, I will present an overview of some of my recent work on this topic. Specifically, I will describe a simple primal-dual algorithm that maintains a (2+epsilon)-approximate maximum {em fractional} matching in G in polylogarithmic update time, and show how to efficiently {em round} this fractional matching into an integral one in this dynamic setting.
Along the way, I will explain some immediate connections between dynamic fractional matchings and the literature on the dynamic set cover.