McGill University - School of Computer Science

# Algorithms Seminar 2003

Everybody is welcome!

 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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer@cs.mcgill.ca. , or sl@jeff.cs.mcgill.ca .