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 |