Computing at Glasgow University
Paper ID: 8027

An n-ary Constraint for the Stable Marriage Problem
Unsworth,C. Prosser,P.

Publication Type: Conference Proceedings
Appeared in: The Fifth Workshop on Modelling and Solving Problems with Constraints, held at the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)
Page Numbers :
Publisher: N/A
Year: 2005

We present an n-ary constraint for the stable marriage problem. This constraint acts between two sets of integer variables where the domains of those variables represent preferences. Our constraint enforces stability and disallows bigamy. For a stable marriage instance with n men and n women we require only one of these constraints, and the complexity of enforcing arc-consistency is O(n^2) which is optimal in the size of input. Our computational studies show that our n-ary constraint is significantly faster and more space efficient than the encodings presented in Gent et al 2001. We also introduce a new problem to the constraint community, the sex-equal stable marriage problem.

PS/PS.GZ Bibtex entry Endnote XML