Streaming Algorithms for Matching Problems

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.