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.
