View 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

Faculty Advisor:

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: For more details about the seminar please visit the website at

Speaker Bio:

Host Faculty: Dr. Arindam Khan