Simple Person's Applied Math Seminar (SPAMS)

Thursday, November 01, 2018 at 6:00pm to 7:00pm

Room 2-132

SPEAKER:   Vishesh Jain  (MIT)

TITLE:   Finding perfect matchings in regular bipartite graphs in O (n log n)  time

ABSTRACT:

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).

 

Event Type

Conferences/Seminars/Lectures

Events By Interest

Academic

Events By Audience

Public

Events By School

School of Science

Website

https://math.mit.edu/seminars/spams/

Department
Department of Mathematics
Add to my calendar

Recent Activity