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

Show simple item record

dc.contributor.author Genc, Begum
dc.contributor.author Siala, Mohamed
dc.contributor.author Simonin, Gilles
dc.contributor.author O'Sullivan, Barry
dc.date.accessioned 2019-05-29T10:42:38Z
dc.date.available 2019-05-29T10:42:38Z
dc.date.issued 2019
dc.identifier.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) en
dc.identifier.startpage 1 en
dc.identifier.endpage 16 en
dc.identifier.uri http://hdl.handle.net/10468/7996
dc.description.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. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher HAL-LAAS Open Archive en
dc.relation.ispartof CPAIOR 2019: Sixteenth International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research
dc.relation.uri https://hal.laas.fr/hal-02062127/document
dc.relation.uri http://cpaior2019.uowm.gr/program/
dc.relation.uri https://hal.laas.fr/hal-02062127
dc.rights © 2019, the Authors. All rights reserved. en
dc.subject Polynomial-time procedure en
dc.subject Reduced rotation en
dc.subject Stable matching en
dc.subject Stable Marriage problem en
dc.subject Stable Roommates problem en
dc.subject Robustness en
dc.subject Meta-heuristics en
dc.subject Complexity en
dc.title An approach to robustness in the Stable Roommates problem and its comparison with the Stable Marriage problem en
dc.type Conference item en
dc.internal.authorcontactother Barry O'Sullivan, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: b.osullivan@cs.ucc.ie en
dc.internal.availability Full text available en
dc.date.updated 2019-03-27T10:47:04Z
dc.description.version Submitted Version en
dc.internal.rssid 479313276
dc.contributor.funder Science Foundation Ireland en
dc.contributor.funder European Regional Development Fund en
dc.description.status Peer reviewed en
dc.internal.copyrightchecked Yes
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Thessaloniki, Greece en
dc.internal.IRISemailaddress b.osullivan@cs.ucc.ie en
dc.identifier.articleid hal-02062127
dc.internal.bibliocheck Not (yet?) published. Check publication status. If applicable, add vol / issue / page range, doi, url, publication date. Amend citation as necessary. Check that copyright statement is correct. en
dc.internal.bibliocheck Published in HAL Archives prior to conference. Check after conference June 2019 for publication details and adjust record and citation accordingly.
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ en


Files in this item

This item appears in the following Collection(s)

Show simple item record

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