An approach to robustness in stable marriage and stable roommates problems

Show simple item record

dc.contributor.advisor O'Sullivan, Barry en
dc.contributor.advisor Siala, Mohamed en
dc.contributor.author Genc, Begum
dc.date.accessioned 2019-08-21T08:58:56Z
dc.date.available 2019-08-21T08:58:56Z
dc.date.issued 2019
dc.date.submitted 2019
dc.identifier.citation Genc, B. 2019. An approach to robustness in stable marriage and stable roommates problems. PhD Thesis, University College Cork. en
dc.identifier.endpage 207 en
dc.identifier.uri http://hdl.handle.net/10468/8361
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. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher University College Cork en
dc.rights © 2019, Begum Genc. en
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/ en
dc.subject Robustness en
dc.subject (a,b)-supermatch en
dc.subject Optimization en
dc.subject Stable marriage en
dc.subject Stable roommates en
dc.title An approach to robustness in stable marriage and stable roommates problems en
dc.type Doctoral thesis en
dc.type.qualificationlevel Doctoral en
dc.type.qualificationname PhD en
dc.internal.availability Full text available en
dc.check.info Not applicable en
dc.description.version Accepted Version
dc.contributor.funder Science Foundation Ireland en
dc.description.status Not peer reviewed en
dc.internal.school Computer Science and Information Technology en
dc.check.type No Embargo Required
dc.check.reason Not applicable en
dc.check.opt-out Not applicable en
dc.thesis.opt-out false
dc.check.embargoformat Embargo not applicable (If you have not submitted an e-thesis or do not want to request an embargo) en
ucc.workflow.supervisor osullivan.barry@ucc.ie
dc.internal.conferring Autumn 2019 en
dc.internal.ricu Insight - Centre for Data Analytics 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

© 2019, Begum Genc. Except where otherwise noted, this item's license is described as © 2019, Begum Genc.
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