Seminars

View all Seminars  |  Download ICal for this event

Some Recent Advances in Dynamic Algorithms for Maximum Matching and Minimum Set Cover (Part 1)

Series: Theory Seminar

Speaker: Dr. Sayan Bhattacharya, Associate Professor, Department of Computer Science, University of Warwick, United Kingdom

Date/Time: Dec 03 16:00:00

Location: Microsoft Teams - ON-LINE

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 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.
<br>
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).
<br>
Along the way, I will explain some immediate connections between dynamic fractional matching algorithms and the literature on dynamic set cover.
<br>
<br>
Microsoft Teams Link:
<br>
<a href="Link
<br>
<br>
<br>
For more details about the seminar please visit the website at Link

Host Faculty: Dr. Arindam Khan