SeminarsView all Seminars | Download ICal for this event
Some Recent Advances in Dynamic Algorithms for Maximum Matching and Minimum Set Cover (Part 2)
Series: Theory Seminar
Speaker: Dr. Sayan Bhattacharya, Associate Professor, Department of Computer Science, University of Warwick, United Kingdom
Date/Time: Dec 10 16:00:00
Location: Microsoft Teams - ON-LINE
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 with small update time. Here, 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 the update time of our algorithm is polylogarithmic in the number of nodes G.
This problem has received considerable attention in the past decade. In these two talks, I will present an overview of some recent advances on this question. Specifically, I will describe a simple primal-dual algorithm that maintains a (2+epsilon)-approximate "fractional" matching in G in polylogarithmic update time (Part 1), and show how to efficiently "round" this fractional matching into an integral one in the dynamic setting (Part 2).
Along the way, I will explain some immediate connections between dynamic fractional matching algorithms and the literature on dynamic set cover.
Microsoft Teams Link:
https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
Host Faculty: Dr. Arindam Khan