UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 5830

A Constraint Programming Approach to the Stable Marriage Problem
Gent,I.P. Irving,R.W. Manlove,D.F. Prosser,P. Smith,B.M.

Publication Type: Conference Proceedings
Appeared in: Proceedings of CP 2001: The 7th International Conference on Principles and Practice of Constraint Programming, volume 2239 of Lecture Notes in Computer Science
Page Numbers : 225-239
Publisher: Springer Verlag
Year: 2001
ISBN/ISSN: 3-540-42863-1

URL: This publication is available at this URL.

Note: (c) Springer-Verlag


Abstract:

The Stable Marriage problem (SM) is an extensively-studied combinatorial problem with many practical applications. In this paper we present two encodings of an instance I of SM as an instance J of a Constraint Satisfaction Problem. We prove that, in a precise sense, establishing arc consistency in J is equivalent to the action of the established Extended Gale/Shapley algorithm for SM on I. As a consequence of this, the man-optimal and woman-optimal stable matchings can be derived immediately. Furthermore we show that, in both encodings, all solutions of I may be enumerated in a failure-free manner. Our results indicate the applicability of Constraint Programming to the domain of stable matching problems in general, many of which are NP-hard.


PDF Bibtex entry Endnote XML