Simple Person's Applied Math Seminar (SPAMS)
Thursday, November 01, 2018 at 6:00pm to 7:00pm
SPEAKER: Vishesh Jain (MIT)
TITLE: Finding perfect matchings in regular bipartite graphs in O (n log n) time
Hall's theorem shows that a d-regular bipartite graph on parts of size n always contains a perfect matching. Such a perfect matching may be found quickly using a variety of methods -- in time O(dn^2) by Ford-Fulkerson, in time O(nd √n by Hopcroft-Karp, and in time O(nd) by Cole-Ost-Schirra, to name a few classic results. Moreover, it is also easily seen that any *deterministic* algorithm must take time Ω(nd) in the worst case. I will present a "shockingly simple"' randomized algorithm due to Goel-Kapralov-Khanna which finds such a perfect matching in expected time O(n log n).