Finding robust solutions to 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 Sierra, Carles
dc.contributor.editor Sierra, Carles
dc.date.accessioned 2018-01-15T15:04:59Z
dc.date.available 2018-01-15T15:04:59Z
dc.date.issued 2017-08
dc.identifier.citation Genc, B., Siala, M., Simonin, G. and O'Sullivan, Barry (2017) 'Finding Robust Solutions to Stable Marriage ', in: Sierra, C. (ed.) Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) Melbourne, Australia, 19-25 August. doi: 10.24963/ijcai.2017/88 en
dc.identifier.startpage 631 en
dc.identifier.endpage 637 en
dc.identifier.isbn 978-0-9992411-0-3
dc.identifier.uri http://hdl.handle.net/10468/5279
dc.identifier.doi 10.24963/ijcai.2017/88
dc.description.abstract We study the notion of robustness in stable matching problems. We first define robustness by introducing (a,b)-supermatches. An (a,b)-supermatch is a stable matching in which if a pairs break up it is possible to find another stable matching by changing the partners of those a pairs and at most b other pairs. In this context, we define the most robust stable matching as a (1,b)-supermatch where b is minimum. We show that checking whether a given stable matching is a (1,b)-supermatch can be done in polynomial time. Next, we use this procedure to design a constraint programming model, a local search approach, and a genetic algorithm to find the most robust stable matching. Our empirical evaluation on large instances show that local search outperforms the other approaches. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher International Joint Conferences on Artificial Intelligence Organization en
dc.relation.ispartof Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)
dc.rights © 2017 International Joint Conferences on Artificial Intelligence All rights reserved. en
dc.subject Constraints en
dc.subject Satisfiability en
dc.subject Knowledge representation en
dc.subject Reasoning and logic en
dc.subject Preferences en
dc.subject Combinatorial heuristic search en
dc.subject Heuristic search en
dc.subject Agent-based systems en
dc.subject Multi-agent systems en
dc.subject Social choice theory en
dc.title Finding robust solutions to stable marriage 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.date.updated 2018-01-15T14:56:37Z
dc.description.version Published Version en
dc.internal.rssid 421919669
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) en
dc.internal.copyrightchecked No !!CORA!! "You can publish any version of the paper published at IJCAI, IF a reference and a link to the copyright holder (IJCAI Organization) are clearly visible ." en
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Melbourne, Australia 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