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