Rotation-based formulation for stable matching

Files in this item

Icon
Name: 4582.pdf
Size: 413.7Kb
Format: PDF
Description: Accepted version
View/Open

Rotation-based formulation for stable matching

Siala, Mohamed; O'Sullivan, Barry
Date: 2017-08-23
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
Full text restriction information: Access to this article is restricted until 12 months after publication by request of the publisher.
Restriction lift date: 2018-08-23
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.
Published Version: 10.1007/978-3-319-66158-2_17

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.

Show full item record

This item appears in the following Collection(s)

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement