2005 | OriginalPaper | Buchkapitel
Specialised Constraints for Stable Matching Problems
verfasst von : Chris Unsworth, Patrick Prosser
Erschienen in: Principles and Practice of Constraint Programming - CP 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The stable marriage problem (SM) and the Hospital / Residents problem (HR) are both stable matching problems. They consist of two sets of objects that need to be matched to each other; in SM men to women, and in HR residents to hospitals. Each set of objects expresses a ranked preference for the objects in the other set, in the form of a preference list. The problem is then to find a matching of one set to the other such that the matching is stable. A matching is stable iff it contains no blocking pairs. A blocking pair in a matching
M
consists of two objects
x
and
y
one from each set(
x
= man and
y
= woman for SM or
x
= hospital and
y
= resident in HR), such that
x
and
y
are not matched in
M
and both
x
and
y
would rather be matched to each other than to there assignment in
M
.