Shuichi Miyazaki (宮崎 修一), Approximation Algorithms for Finding Maximum Stable Matchings

Approximation algorithms for finding maximum stable matchings
Shuichi Miyazaki (宮崎 修一)
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.

Tags:

This entry was posted on Thursday, September 16th, 2010 at 3:50 pm and is filed under 2010, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.