ICS Theory Group

ICS 269, Spring 2005: Theory Seminar

22 Apr 2005:
Popular Matchings
Presented by Matt Nguyen

This talk is a presentation of "Popular Matchings" by David J. Abraham, Rob W. Irving, Kurt Mehlhorn and Kavitha Telikepalli from SODA 2005.

The authors consider the problem of matching a set of applicants to a set of posts. Each applicant contains a preference list ranking each post by preference. A matching M is then said to be popular if there is no matching M' such that the number of applicants preferring M' to M exceeds the number of applicants preferring M to M'. The authors give an O(sqrt(n) m ) time algorithm finding the largest popular matching if it exists. Note that this is a special case of the stable marriage problem - All popular matchings are stable.