| DATE: | Thursday, March 6th |
| TIME: | 4:00 PM - 5:00 PM |
| PLACE: | McConnell 103 |
| TITLE: | Approximability of Stable Marriage with Incomplete Lists and Ties |
| SPEAKER: | Shuichi Miyazaki Academic Center for Computing and Media Studies, Kyoto University, Japan |
In this talk, we show basic properties and our results on the stable marriage problem.
In the original stable marriage problem, each person submits a preference list that ranks "all" persons in the opposite sex in a "total order". A matching M is called stable if there is no pair (m,w) such that (i) m and w are not matched in M, (ii) m prefers w to his partner in M and (iii) w prefers m to her partner in M. It is a well known fact that any stable marriage instance permits at least one stable matching and the Gale-Shapley algorithm finds one in polynomial time.
One natural relaxation is to allow ties in preference lists. In this case, there always exists a (weakly) stable matching and it is easy to find one. Another relaxation is to allow incomplete lists, i.e., one does not have to write all the people in the opposite sex. In this case, a stable matching may not a perfect matching but for a fixed instance, all stable matchings are of the same size.
However, if we allow "both" ties and incomplete lists, then there can be stable matchings of different sizes. This gives rise to the problem of finding a maximum stable matching, denoted by MAX SMTI.
We show that MAX SMTI is NP-hard, and furthermore, APX-hard. As for
approximability, it is easy to approximate this problem within an
approximation factor of two. We give polynomial time approximation
algorithms with performance ratio less than two for restricted but still
APX-hard cases.