BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/615
DTSTAMP:20230914T125931Z
SUMMARY:Dynamic Primal Dual Algorithms for Vertex Cover and Matching
DESCRIPTION:Speaker: Sayan Bhattacharya (Institute of Mathematical Sciences
\nIV Cross Road\, CIT Campus\nTaramani\nChennai 600113)\n\nAbstract: \nAbs
tract: Consider a scenario where we are given an input graph $G = (V\, E)$
\, and at each time-step either a new edge is inserted into the graph or a
n already existing edge is deleted from the graph. In this dynamic setting
\, we want to maintain an approximately minimum vertex cover and an approx
imately maximum matching in $G$.\n\nOur main result is a deterministic pri
mal-dual algorithm for this problem. The algorithm maintains a $(2+\\epsil
on)$-approximate minimum vertex cover in $O(\\log n/\\epsilon^2)$ amortize
d update time\, where n denotes the number of nodes. This answers an open
question from Onak and Rubinfield [STOC' 2010]. We can also maintain a $(3
+\\epsilon)$-approximate maximum matching in $O(m^{1/3})$ amortized update
time\, where m denotes the number of edges in the graph.\n\nWe also descr
ibe extensions of our framework to dynamic set cover and dynamic b-matchin
g problems (joint work with Monika Henzinger and Guiseppe Italiano\, ased
on work that appeared in SODA 2015 and ICALP 2015).\n
URL:https://www.tcs.tifr.res.in/web/events/615
DTSTART;TZID=Asia/Kolkata:20150812T143000
DTEND;TZID=Asia/Kolkata:20150812T153000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR