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

Simple item page
dc.contributor.authorGenc, Begum
dc.contributor.authorSiala, Mohamed
dc.contributor.authorSimonin, Gilles
dc.contributor.authorO'Sullivan, Barry
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderEuropean Regional Development Funden
dc.date.accessioned2019-05-29T10:42:38Z
dc.date.available2019-05-29T10:42:38Z
dc.date.issued2019
dc.date.updated2019-03-27T10:47:04Z
dc.description.abstractRecently 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.description.statusPeer revieweden
dc.description.versionSubmitted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.articleidhal-02062127
dc.identifier.citationGenc, 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.endpage16en
dc.identifier.startpage1en
dc.identifier.urihttps://hdl.handle.net/10468/7996
dc.language.isoenen
dc.publisherHAL-LAAS Open Archiveen
dc.relation.ispartofCPAIOR 2019: Sixteenth International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.urihttps://hal.laas.fr/hal-02062127/document
dc.relation.urihttp://cpaior2019.uowm.gr/program/
dc.relation.urihttps://hal.laas.fr/hal-02062127
dc.rights© 2019, the Authors. All rights reserved.en
dc.subjectPolynomial-time procedureen
dc.subjectReduced rotationen
dc.subjectStable matchingen
dc.subjectStable Marriage problemen
dc.subjectStable Roommates problemen
dc.subjectRobustnessen
dc.subjectMeta-heuristicsen
dc.subjectComplexityen
dc.titleAn approach to robustness in the Stable Roommates problem and its comparison with the Stable Marriage problemen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
19-CPAIOR.pdf
Size:
440.5 KB
Format:
Adobe Portable Document Format
Description:
Submitted Version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items