TY - GEN
T1 - On the complexity of robust stable marriage
AU - Genc, Begum
AU - Siala, Mohamed
AU - Simonin, Gilles
AU - O’Sullivan, Barry
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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 NP -complete, we first introduce a SAT formulation that is NP -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.
AB - 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 NP -complete, we first introduce a SAT formulation that is NP -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.
UR - https://www.scopus.com/pages/publications/85038209938
U2 - 10.1007/978-3-319-71147-8_30
DO - 10.1007/978-3-319-71147-8_30
M3 - Conference proceeding
AN - SCOPUS:85038209938
SN - 9783319711461
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 441
EP - 448
BT - Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Proceedings
A2 - Gao, Xiaofeng
A2 - Du, Hongwei
A2 - Han, Meng
PB - Springer Verlag
T2 - 11th International Conference on Combinatorial Optimization and Applications, COCOA 2017
Y2 - 16 December 2017 through 18 December 2017
ER -