Big Data Analytics 2013
Big Data Analytics 2013

Keynote talk

Fast Algorithms for Perfect Matching in Regular Bipartite Graphs

Sanjeev Khanna, University of Pennsylvania

The problem of finding a perfect matching in a regular bipartite graph is a classical problem with applications to edge-colorings, routing, and scheduling, and is also closely related to the Birkhoff-von Neumann decomposition of doubly stochastic matrices. A sequence of improvements over the years have culminated in a linear-time algorithm for this problem. In this talk, we will show that graph sparsification and random walks can be used to obtain surprisingly fast sublinear time algorithms for this problem. Our approach also yields an efficient algorithm for computing the Birkhoff-von-Neumann decomposition of a doubly-stochastic matrix.