Approximation algorithms for finding maximum stable matchings
Shuichi Miyazaki (宮崎 修一)
Academic Center for Computing and Media Studies, Kyoto University, Kyoto, Japan
Academic Center for Computing and Media Studies, Kyoto University, Kyoto, Japan
2010/10/15 Fri 4PM-5PM
The stable marriage problem is a classical matching problem. An input consists of the set of men, the set of women, and each person’s preference list that orders the members of the opposite sex according to the preference. The problem asks to find a stable matching, that is, a matching that contains no (man, woman) pair, each of which prefers the other to his/her current partner in the matching.
One of the practical extensions is to allow participants to use ties in preference lists and to exclude unacceptable persons from lists. In this variant, finding a stable matching of maximum size is NP-hard. In this talk, we give some of the approximability results on this problem.