Talks & Seminars
Title: Streaming Algorithms for Matching Problems
Dr. Sagar Kale, EPFL, Lausanne
Date & Time: October 16, 2019 14:15
Venue: Dept. of CSE, Room no. 109, 01st Floor, New CSE/CC Bldg.
The advent of big data necessitated design of algorithms that could cope with it. Streaming algorithms are viable for big data because they process their input sequentially and use a small amount of working memory. In this talk, I will present my research on streaming algorithms for matching problems. Matching problems have played a significant historical role in not just combinatorial optimization specifically but computer science at large and are our benchmark problems for development and understanding of a computational model. Indeed, studying them in the streaming model has led me to fastest algorithms for some combinatorial optimization problems---streaming or otherwise. In 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-studied generalization of maximum matching where the graph is edge-weighted, and, in a further generalization, a submodular function is defined on the edges. Submodular functions have received a lot of attention in theoretical computer science as well as, more recently, in machine learning. I will 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 in the MapReduce framework. I will conclude with future research directions.
Speaker Profile:
Details available at: https://sagark4.github.io/
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback