BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/610
DTSTAMP:20230914T125931Z
SUMMARY:Fully Dynamic $(1+\\epsilon)$-Approximate Matchings
DESCRIPTION:Speaker: Manoj Gupta (Xerox Research Centre India\nEtamin Block
  3\, 4th Floor\, Wing-A Prestige\nTechnology Park II\, Marathahalli - Sara
 japur\nOuter Ring Road\nBangalore 560103\n )\n\nAbstract: \nAbstract : We
  study data structures that maintain approximate maximum matchings in grap
 hs under edge insertions/deletions. Our main result is a data structure th
 at maintains a matching whose size is at least $(1 - \\epsilon)$ of the ma
 ximum in worst case $O(\\sqrt{m}\\epsilon^{-2})$ per update. It is the fir
 st data structure that is able to maintain arbitrary quality approximation
 s on sparse graphs in sublinear time per update.\n\nOur results of maximum
  cardinality matching easily extend to maximum weighted matching. Using kn
 own schemes\, we first obtain a $(3+\\epsilon)$ approximation of maximum w
 eighted matching with $O( \\sqrt m \\epsilon^{-2} \\log N)$ update time. U
 sing intricate rounding schemes\, we then obtain a $(1+\\epsilon)$ approxi
 mation of maximum matching in $O( \\sqrt{m} \\epsilon^{-2 - O(\\epsilon^{-
 1})} \\log N)$ update time. It is the first data-structure which maintains
  arbitrary quality approximation on a weighted graph.\n \n
URL:https://www.tcs.tifr.res.in/web/events/610
DTSTART;TZID=Asia/Kolkata:20150723T160000
DTEND;TZID=Asia/Kolkata:20150723T170000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR