BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1244
DTSTAMP:20230914T125956Z
SUMMARY:Streaming Algorithms for Maximum Weighted Matching
DESCRIPTION:Speaker: Pavel Dvorak\n\nAbstract: \nI will talk about the maxi
mum weighted matching problem in the streaming model. In this model\, an a
lgorithm receives edges of a graph one by one. When the stream ends\, it s
hould output an approximation of the maximum weighted matching of the inpu
t graph using only linear (or subquadratic) memory. First\, I will present
an algorithm of Paz and Swartzmann\, who gave a 2-approximation for this
problem. Further\, I will talk about how to use this algorithm for design
algorithms in sliding window model. In this model\, when an edge arrives\,
the algorithm should output an approximation of the maximum weighted matc
hing in a graph spanned by last L edges\, where L is a parameter of the mo
del.\n\nThis is a joint work with Cezar-Mihail Alexandru\, Christian Konra
d\, and Kheeran K. Naidu.\n
URL:https://www.tcs.tifr.res.in/web/events/1244
DTSTART;TZID=Asia/Kolkata:20221014T160000
DTEND;TZID=Asia/Kolkata:20221014T170000
END:VEVENT
END:VCALENDAR