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