An Approach to Robustness in the Stable Roommates Problem and its Comparison with the Stable Marriage Problem - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Access content directly
Conference Papers Year : 2019

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

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.
Fichier principal
Vignette du fichier
19-CPAIOR.pdf (424.68 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02062127 , version 1 (08-03-2019)

Identifiers

Cite

Begum Genc, Mohamed Siala, Gilles Simonin, Barry O'Sullivan. 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, Jun 2019, Thessaloniki, Greece. ⟨10.1007/978-3-030-19212-9_21⟩. ⟨hal-02062127⟩
30 View
1 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More