BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20211203T120000Z
UID:7f2b9f41ead02d2bbb21ae2a26912bdb-222
DTSTAMP:19700101T120016Z
DESCRIPTION:Some Recent Advances in Dynamic Algorithms for Maximum Matching and Minimum Set Cover (Part 1)
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/222/some-recent-advances-in-dynamic-algorithms-for-maximum-matching-and-minimum-set-cover-part-1/
SUMMARY: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="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">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</a>
<br>
<br>
<br>
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
DTSTART:20211203T120000Z
END:VEVENT
END:VCALENDAR