An approach to robustness in the Stable Roommates problem and its comparison with the Stable Marriage problem

Loading...
Thumbnail Image
Files
19-CPAIOR.pdf(440.5 KB)
Submitted Version
Date
2019
Authors
Genc, Begum
Siala, Mohamed
Simonin, Gilles
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
HAL-LAAS Open Archive
Published Version
Research Projects
Organizational Units
Journal Issue
Abstract
Recently a robustness notion for matching problems based on the concept of a (a, b)-supermatch is proposed for the Stable Marriage problem (SM). In this paper we extend this notion to another matching problem, namely the Stable Roommates problem (SR). We define a polynomial-time procedure based on the concept of reduced rotation poset to verify if a stable matching is a (1, b)-supermatch. Then, we adapt a local search and a genetic local search procedure to find the (1, b)-supermatch that minimises b in a given SR instance. Finally, we compare the two models and also create different SM and SR instances to present empirical results on the robustness of these instances.
Description
Keywords
Polynomial-time procedure , Reduced rotation , Stable matching , Stable Marriage problem , Stable Roommates problem , Robustness , Meta-heuristics , Complexity
Citation
Genc, B., Siala, M., Simonin, G. and O’Sullivan, B. (2019) ‘An approach to robustness in the Stable Roommates problem and its comparison with the Stable Marriage problem’, Sixteenth International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Thessaloniki, Greece, 4-7 June, pp. 1-16. Available at: https://hal.laas.fr/hal-02062127 (Accessed: 29 May, 2019)
Copyright
© 2019, the Authors. All rights reserved.