On the complexity of Robust Stable Marriage

Simple item page
dc.contributor.authorGenc, Begum
dc.contributor.authorSiala, Mohamed
dc.contributor.authorSimonin, Gilles
dc.contributor.authorO'Sullivan, Barry
dc.contributor.editorGao, Xiaofeng
dc.contributor.editorDu, Hongwei
dc.contributor.editorHan, Meng
dc.date.accessioned2018-01-15T12:37:58Z
dc.date.available2018-01-15T12:37:58Z
dc.date.issued2017-11-16
dc.date.updated2018-01-12T12:34:00Z
dc.description.abstractRobust Stable Marriage (RSM) is a variant of the classical Stable Marriage problem, where the robustness of a given stable matching is measured by the number of modifications required for repairing it in case an unforeseen event occurs. We focus on the complexity of finding an (a, b)-supermatch. An (a, b)-supermatch is defined as a stable matching in which if any a (non-fixed) men/women break up it is possible to find another stable matching by changing the partners of those a men/women and also the partners of at most b other couples. In order to show deciding if there exists an (a, b)-supermatch is NPNP -complete, we first introduce a SAT formulation that is NPNP -complete by using Schaefer’s Dichotomy Theorem. Then, we show the equivalence between the SAT formulation and finding a (1, 1)-supermatch on a specific family of instances.en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationGenc, B., Siala, M., Simonin, G. and O’Sullivan, B. (2017) 'On the Complexity of Robust Stable Marriage', in Gao, X., Du, H. & Han, M. (eds.) Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II, Lecture Notes in Computer Science, LCNS vol. 10335, Cham: Springer International Publishing, pp. 441-448. doi: 10.1007/978-3-319-71147-8_30en
dc.identifier.doi10.1007/978-3-319-71147-8_30
dc.identifier.endpage448en
dc.identifier.isbn978-3-319-71147-8
dc.identifier.journaltitleLecture Notes in Computer Scienceen
dc.identifier.startpage441en
dc.identifier.urihttps://hdl.handle.net/10468/5277
dc.identifier.volume10335en
dc.language.isoenen
dc.publisherSpringer International Publishingen
dc.relation.ispartofCombinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II. Lecture Notes in Computer Science, vol 10628
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.rights© Springer International Publishing AG 2017. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-71147-8_30en
dc.subjectRobust Stable Marriage (RSM)en
dc.subjectStable Marriage problemen
dc.subjectCombinatorial optimizationen
dc.subjectA-stableen
dc.subjectClassical stable marriagesen
dc.subjectDichotomy theoremen
dc.subjectNP Completeen
dc.subjectStable marriagesen
dc.subjectStable matchingen
dc.titleOn the complexity of Robust Stable Marriageen
dc.typeBook chapteren
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
4581.pdf
Size:
108.68 KB
Format:
Adobe Portable Document Format
Description:
Accepted 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