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