TY - GEN
T1 - An Approach to Robustness in the Stable Roommates Problem and Its Comparison with the Stable Marriage Problem
AU - Genc, Begum
AU - Siala, Mohamed
AU - Simonin, Gilles
AU - O’Sullivan, Barry
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85066845298
U2 - 10.1007/978-3-030-19212-9_21
DO - 10.1007/978-3-030-19212-9_21
M3 - Conference proceeding
AN - SCOPUS:85066845298
SN - 9783030192112
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 320
EP - 336
BT - Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 16th International Conference, CPAIOR 2019, Proceedings
A2 - Stergiou, Kostas
A2 - Rousseau, Louis-Martin
PB - Springer Verlag
T2 - 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2019
Y2 - 4 June 2019 through 7 June 2019
ER -