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 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.
This talk considers the question if a perfect matching can be computed in a regular
bipartite graph in time that is sub-linear in the number of edges. We show that using
randomization, one can obtain surprisingly efficient sub-linear time algorithms for this
problem. In contrast, we show that no deterministic algorithm can do better than linear-time.
This is based on joint work with Ashish Goel and Michael Kapralov at Stanford University.
Copyright. All Rights Reserved.