{"id":{"repo_id":"cork","oai_identifier":"oai:cora.ucc.ie:10468/8361"},"canonical_url":"https://search.dev.ndltd.org/etd/cork/oai:cora.ucc.ie:10468/8361","repository":{"repo_id":"cork","name":"University College Cork","base_url":"https://cora.ucc.ie/server/oai/request"},"display":{"title":"An approach to robustness in stable marriage and stable roommates problems","abstract":"This dissertation focuses on a novel concept of robustness within the context of matching problems. Our robustness notion for the stable matching framework is motivated by the unforeseen events that may occur after a matching is computed. We define the notion of (a,b)-supermatches as a measure of robustness of a matching. An (a,b)-supermatch characterizes a stable matching such that if any combination of 'a' pairs want to leave the matching, there exists an alternative matching in which those 'a' pairs are assigned new partners, and in order to obtain the new assignment at most 'b' other pairs are broken. We first formally define the notion of (a,b)-supermatches by using one of the most famous matching problems, namely the Stable Marriage problem (SM), as the platform. We name the problem of finding an (a,b)-supermatch to the SM as the Robust Stable Marriage problem (RSM). Subsequently, we prove that RSM is NP-hard, and the decision problem for the case where a=1 (i.e. deciding if there exists a (1,b)-supermatch) is NP-complete. We also develop a constraint programming model and a number of meta-heuristic approaches to find a (1,b)-supermatch that minimizes the value of 'b' for the RSM. Following the results on the RSM, we extend the notion of (a,b)-supermatches to the Stable Roommates problem (SR), namely, the Robust Stable Roommates problem (RSR). We show that the NP-hardness is also valid for the RSR, and we also define a polynomial-time procedure for the RSR to decide if a given stable matching is a (1,b)-supermatch. Similarly, we provide a number of meta-heuristic models to solve the optimization problem for finding a (1,b)-supermatch that minimizes the value of 'b'. We conclude this dissertation by providing some empirical results on the robustness of different datasets of RSM and RSR instances.","abstract_html":"This dissertation focuses on a novel concept of robustness within the context of matching problems. Our robustness notion for the stable matching framework is motivated by the unforeseen events that may occur after a matching is computed. We define the notion of (a,b)-supermatches as a measure of robustness of a matching. An (a,b)-supermatch characterizes a stable matching such that if any combination of 'a' pairs want to leave the matching, there exists an alternative matching in which those 'a' pairs are assigned new partners, and in order to obtain the new assignment at most 'b' other pairs are broken. We first formally define the notion of (a,b)-supermatches by using one of the most famous matching problems, namely the Stable Marriage problem (SM), as the platform. We name the problem of finding an (a,b)-supermatch to the SM as the Robust Stable Marriage problem (RSM). Subsequently, we prove that RSM is NP-hard, and the decision problem for the case where a=1 (i.e. deciding if there exists a (1,b)-supermatch) is NP-complete. We also develop a constraint programming model and a number of meta-heuristic approaches to find a (1,b)-supermatch that minimizes the value of 'b' for the RSM. Following the results on the RSM, we extend the notion of (a,b)-supermatches to the Stable Roommates problem (SR), namely, the Robust Stable Roommates problem (RSR). We show that the NP-hardness is also valid for the RSR, and we also define a polynomial-time procedure for the RSR to decide if a given stable matching is a (1,b)-supermatch. Similarly, we provide a number of meta-heuristic models to solve the optimization problem for finding a (1,b)-supermatch that minimizes the value of 'b'. We conclude this dissertation by providing some empirical results on the robustness of different datasets of RSM and RSR instances.","abstract_has_math":false,"creators":["Genc, Begum"],"institution":"University College Cork","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["O'Sullivan, Barry","Siala, Mohamed"],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-07-24T01:46:55Z","subjects":["Robustness","(a,b)-supermatch","Optimization","Stable marriage","Stable roommates"],"languages":["en"],"rights":["© 2019, Begum Genc."],"rights_urls":["http://creativecommons.org/licenses/by-nc-nd/3.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/10468/8361","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["O'Sullivan, Barry","Siala, Mohamed"]},{"key":"dc:creator","label":"Author","values":["Genc, Begum"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-08-21T08:58:56Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2019-08-21T08:58:56Z"]},{"key":"dc:date.issued","label":"Date","values":["2019"]},{"key":"dc:publisher","label":"Institution","values":["University College Cork"]},{"key":"dc:type","label":"Dc Type","values":["Doctoral thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["PhD"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Robustness","(a,b)-supermatch","Optimization","Stable marriage","Stable roommates"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["© 2019, Begum Genc."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://creativecommons.org/licenses/by-nc-nd/3.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10468/8361"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This dissertation focuses on a novel concept of robustness within the context of matching problems. Our robustness notion for the stable matching framework is motivated by the unforeseen events that may occur after a matching is computed. We define the notion of (a,b)-supermatches as a measure of robustness of a matching. An (a,b)-supermatch characterizes a stable matching such that if any combination of 'a' pairs want to leave the matching, there exists an alternative matching in which those 'a' pairs are assigned new partners, and in order to obtain the new assignment at most 'b' other pairs are broken. We first formally define the notion of (a,b)-supermatches by using one of the most famous matching problems, namely the Stable Marriage problem (SM), as the platform. We name the problem of finding an (a,b)-supermatch to the SM as the Robust Stable Marriage problem (RSM). Subsequently, we prove that RSM is NP-hard, and the decision problem for the case where a=1 (i.e. deciding if there exists a (1,b)-supermatch) is NP-complete. We also develop a constraint programming model and a number of meta-heuristic approaches to find a (1,b)-supermatch that minimizes the value of 'b' for the RSM. Following the results on the RSM, we extend the notion of (a,b)-supermatches to the Stable Roommates problem (SR), namely, the Robust Stable Roommates problem (RSR). We show that the NP-hardness is also valid for the RSR, and we also define a polynomial-time procedure for the RSR to decide if a given stable matching is a (1,b)-supermatch. Similarly, we provide a number of meta-heuristic models to solve the optimization problem for finding a (1,b)-supermatch that minimizes the value of 'b'. We conclude this dissertation by providing some empirical results on the robustness of different datasets of RSM and RSR instances."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["An approach to robustness in stable marriage and stable roommates problems"]}]}],"canonical_facts":{"dc:contributor.advisor":["O'Sullivan, Barry","Siala, Mohamed"],"dc:creator":["Genc, Begum"],"dc:date.accessioned":["2019-08-21T08:58:56Z"],"dc:date.available":["2019-08-21T08:58:56Z"],"dc:date.issued":["2019"],"dc:description.abstract":["This dissertation focuses on a novel concept of robustness within the context of matching problems. Our robustness notion for the stable matching framework is motivated by the unforeseen events that may occur after a matching is computed. We define the notion of (a,b)-supermatches as a measure of robustness of a matching. An (a,b)-supermatch characterizes a stable matching such that if any combination of 'a' pairs want to leave the matching, there exists an alternative matching in which those 'a' pairs are assigned new partners, and in order to obtain the new assignment at most 'b' other pairs are broken. We first formally define the notion of (a,b)-supermatches by using one of the most famous matching problems, namely the Stable Marriage problem (SM), as the platform. We name the problem of finding an (a,b)-supermatch to the SM as the Robust Stable Marriage problem (RSM). Subsequently, we prove that RSM is NP-hard, and the decision problem for the case where a=1 (i.e. deciding if there exists a (1,b)-supermatch) is NP-complete. We also develop a constraint programming model and a number of meta-heuristic approaches to find a (1,b)-supermatch that minimizes the value of 'b' for the RSM. Following the results on the RSM, we extend the notion of (a,b)-supermatches to the Stable Roommates problem (SR), namely, the Robust Stable Roommates problem (RSR). We show that the NP-hardness is also valid for the RSR, and we also define a polynomial-time procedure for the RSR to decide if a given stable matching is a (1,b)-supermatch. Similarly, we provide a number of meta-heuristic models to solve the optimization problem for finding a (1,b)-supermatch that minimizes the value of 'b'. We conclude this dissertation by providing some empirical results on the robustness of different datasets of RSM and RSR instances."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["https://hdl.handle.net/10468/8361"],"dc:language.iso":["en"],"dc:publisher":["University College Cork"],"dc:rights":["© 2019, Begum Genc."],"dc:rights.uri":["http://creativecommons.org/licenses/by-nc-nd/3.0/"],"dc:subject":["Robustness","(a,b)-supermatch","Optimization","Stable marriage","Stable roommates"],"dc:title":["An approach to robustness in stable marriage and stable roommates problems"],"dc:type":["Doctoral thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["PhD"]},"updated_at":"2026-07-24T01:46:55Z"}