Algorithms for bipartite matching problems with connections to sparsification and streaming

The need to process massive modern data sets necessitates rethinking of some classical algorithmic solutions from the point of view of modern data processing architectures. Over the past years sparsification has emerged as an important primitive in the algorithmic toolkit for graph algorithms that allows one to obtain a small space representation that approximately preserves some useful properties of the graph. This talk is centered around two topics. First, we give new algorithms for some bipartite matching problems, which use both sparsification and random walks in novel ways. Second, we give efficient algorithms for constructing sparsifiers on modern computing platforms.

In the first part of the talk we consider the problem of finding perfect matchings in regular bipartite graphs, a classical problem with applications to edge-colorings, routing and scheduling. A sequence of improvements over the years have culminated in a linear-time algorithm. We use both sparsification and random walks to obtain efficient sublinear time algorithms for the problem. In particular, we give an algorithm that recovers a perfect matching in O(n log n) time, where n is the number of vertices in the graph, when the graph is given in adjacency array representation. The runtime is within O(log n) of output complexity, essentially closing the problem. Our approach also yields extremely efficient and easy to implement algorithms for edge-coloring bipartite multigraphs and computing the Birkhoff-von-Neumann decomposition of a doubly-stochastic matrix.

In the second part of the talk we describe an efficient algorithm for single pass graph sparsification in distributed stream processing systems such as Twitter’s recently introduced Storm. We also present a novel approach to obtaining spectral sparsifiers, based on a new notion of distance between nodes in a graph related to shortest path distance on random samples of the graph. Finally, in the last part of the talk we introduce and study a notion of sparsification relevant to matching problems in general graphs, and show applications to the problem of approximating maximum matchings in a single pass in the streaming model.

Speaker Details

Michael Kapralov is a PhD student at the Institute for Computational and Mathematical Engineering at Stanford University, advised by Professor Ashish Goel. His main research interests are in combinatorial optimization, as well as problems motivated by modern data models, such as online and streaming algorithms and differential privacy. Michael graduated from St. Petersburg State University, Russia, in 2005 with a BSc in computer science, and University of Central Florida in 2007 with MSc in applied mathematics. He enrolled in the PhD program at Stanford in 2007, with an expected graduation date of June 2012.

Date:
Speakers:
Michael Kapralov
Affiliation:
Stanford University
    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks