BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/750
DTSTAMP:20230914T125936Z
SUMMARY:New Approximation Algorithms for Dynamic Matching and Vertex Cover
DESCRIPTION:Speaker: Sayan Bhattacharya (Institute of Mathematical Sciences
\nIV Cross Road\nCIT Campus\nTaramani\nChennai 600113)\n\nAbstract: \nWe c
onsider the problem of maintaining a matching and a vertex cover of approx
imately maximum (resp. minimum) size in a dynamic graph under a sequence o
f edge insertions and deletions. In recent years\, a significant body of w
ork has been devoted to this problem. Using a primal-dual framework\, we f
irst show how to maintain a $(2+\\epsilon)$ approximate maximum fractional
matching and minimum vertex cover in $O(\\log n/\\epsilon^2)$ amortized u
pdate time\, where n is the number of nodes in the input graph. Next\, we
show how to perform `deterministic rounding' efficiently in a dynamic sett
ing\, thereby converting the fractional matching maintained by the previou
s algorithm into an integral matching. Finally\, we show how to make the u
pdate time of our fractional matching algorithm worst case\, thereby getti
ng the first non-trivial dynamic algorithm that is deterministic and has $
O(\\mathrm{poly} \\log n)$ worst case update time. We conclude by pointing
out some interesting open problems in this area (joint work with M. Henzi
nger and G. Italiano (SODA 2015) and M. Henzinger and D. Nanongkai (STOC 2
016\, SODA 2017)).\n
URL:https://www.tcs.tifr.res.in/web/events/750
DTSTART;TZID=Asia/Kolkata:20170131T160000
DTEND;TZID=Asia/Kolkata:20170131T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR