BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1003
DTSTAMP:20230914T125946Z
SUMMARY:Streaming Algorithms for Matching Problems
DESCRIPTION:Speaker: Sagar Kale (EPFL\, Lausanne\nSwitzerland)\n\nAbstract:
\nAbstract: The advent of big data necessitated design of algorithms that
could cope with it. Streaming algorithms are viable for big data becaus
e they process their input sequentially and use a small amount of working
memory. In this talk\, I will present my research on streaming algorithm
s for matching problems. Matching problems have played a significant his
torical role in not just combinatorial optimization specifically but compu
ter science at large and are our benchmark problems for development and un
derstanding of a computational model.\nIndeed\, studying them in the strea
ming model has led me to fastest algorithms for some combinatorial optimiz
ation problems---streaming or otherwise.\nIn the maximum matching problem\
, edges of the input graph arrive one-by-one in the stream and the goal is
to compute a matching of large size. Weighted matching is a well-studie
d generalization of maximum matching where the graph is edge-weighted\, an
d\, in a further generalization\, a submodular function is defined on the
edges.\nSubmodular functions have received a lot of attention in theoretic
al computer science as well as\, more recently\, in machine learning.\nI w
ill discuss a reduction from submodular matching to weighted matching that
also extends to streaming algorithms for very general constraints such as
matroids. Then I will give an overview of how to obtain almost optimal
weighted matchings in constant number of passes over the stream and also i
n the MapReduce framework. I will conclude with future research directio
ns.\n
URL:https://www.tcs.tifr.res.in/web/events/1003
DTSTART;TZID=Asia/Kolkata:20191007T110000
DTEND;TZID=Asia/Kolkata:20191007T120000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR