Paper ID: 8027
An n-ary Constraint for the Stable Marriage Problem
The Fifth Workshop on Modelling and Solving Problems with Constraints, held at the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)
Page Numbers :
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.