Stable marriage with ties and unacceptable partners
David Manlove, University of Glasgow, UK

Abstract:
An instance of the classical stable marriage problem involves n men 
and n women, and each person ranks all n members of the opposite sex
in strict order of preference. A solution to the problem is a stable
matching, i.e., a complete matching of the men and women such that
no unmatched pair prefer each other to their partners in the matching.
An interesting extension to the problem occurs if we permit each 
person to express ties and unacceptable partners in their preference
list. 

   In this talk, I will summarise briefly the background to the stable
marriage problem, and will describe some of the algorithmic results
relating to the stable marriage problem in this extended setting, where
a preference list no longer needs to be strictly ordered and complete. 
The work is applicable to student-hospital matching schemes, such as 
the National Resident Matching Program in the US.

This is joint work with Rob Irving