Access to this article is restricted until 12 months after publication by request of the publisher.. Restriction lift date: 2018-08-23
Rotation-based formulation for stable matching
Loading...
Files
Accepted version
Date
2017-08-23
Authors
Siala, Mohamed
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
Springer International Publishing
Published Version
Abstract
We introduce new CP models for the many-to-many stable matching problem. We use the notion of rotation to give a novel encoding that is linear in the input size of the problem. We give extra filtering rules to maintain arc consistency in quadratic time. Our experimental study on hard instances of sex-equal and balanced stable matching shows the efficiency of one of our propositions as compared with the state-of-the-art constraint programming approach.
Description
Keywords
CP models , Stable marriage (SM) problem , Constraint programming , Balanced stable matching , Constraint theory , Arc consistency , Constraint programming , Filtering rules , Hard instances , Quadratic time , Stable matching , Stable matching problem , State of the art , Computer programming
Citation
Siala, M. and O’Sullivan, B. (2017) 'Rotation-Based Formulation for Stable Matching', in Beck, J.C. (ed.) Principles and Practice of Constraint Programming: 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 – September 1, 2017, Lecture Notes in Computer Science, LCNS vol. 10416, Cham: Springer International Publishing, pp. 262-277.
Copyright
© Springer International Publishing AG 2017. The final publication is available at Springer via http://dx.doi.org/ 10.1007/978-3-319-66158-2_17