On the complexity of Robust Stable Marriage

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.contributor.editor Gao, Xiaofeng
dc.contributor.editor Du, Hongwei
dc.contributor.editor Han, Meng
dc.date.accessioned 2018-01-15T12:37:58Z
dc.date.available 2018-01-15T12:37:58Z
dc.date.issued 2017-11-16
dc.identifier.citation Genc, 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_30 en
dc.identifier.volume 10335 en
dc.identifier.startpage 441 en
dc.identifier.endpage 448 en
dc.identifier.isbn 978-3-319-71147-8
dc.identifier.uri http://hdl.handle.net/10468/5277
dc.identifier.doi 10.1007/978-3-319-71147-8_30
dc.description.abstract Robust 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.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer International Publishing en
dc.relation.ispartof Combinatorial 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.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_30 en
dc.subject Robust Stable Marriage (RSM) en
dc.subject Stable Marriage problem en
dc.subject Combinatorial optimization en
dc.subject A-stable en
dc.subject Classical stable marriages en
dc.subject Dichotomy theorem en
dc.subject NP Complete en
dc.subject Stable marriages en
dc.subject Stable matching en
dc.title On the complexity of Robust Stable Marriage en
dc.type Book chapter en
dc.type Conference item en
dc.internal.authorcontactother Mohamed Siala, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: mohamed.siala@insight-centre.org en
dc.internal.availability Full text available en
dc.check.info Access to this article is restricted until 12 months after publication by request of the publisher. en
dc.check.date 2018-11-16
dc.date.updated 2018-01-12T12:34:00Z
dc.description.version Accepted Version en
dc.internal.rssid 421497209
dc.description.status Peer reviewed en
dc.identifier.journaltitle Lecture Notes in Computer Science en
dc.internal.copyrightchecked No !!CORA!! en
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Shanghai, China en
dc.internal.placepublication Cham en
dc.internal.IRISemailaddress mohamed.siala@insight-centre.org en
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