You are here

An Approach to Robustness in the Stable Roommates Problem and its Comparison with the Stable Marriage Problem

Authors: 

Begum Genc, Mohamed Siala, Gilles Simonin, Barry O'Sullivan

Publication Type: 
Refereed Conference Meeting Proceeding
Abstract: 
Recently a robustness notion for matching problems based on the concept of an (a,b)-supermatch, was 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. 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.
Conference Name: 
Sixteenth International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2019)
Digital Object Identifer (DOI): 
10.1007/978-3-030-19212-9_21
Publication Date: 
07/02/2019
Volume: 
11494
Conference Location: 
Greece
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No