| Title | : | Streaming Algorithms for Matching Problems |
| Speaker | : | Sagar Kale (EPFL, Lausanne) |
| Details | : | Fri, 11 Oct, 2019 3:00 PM @ AM Turing Hall |
| Abstract: | : | 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. |
