Finding robust solutions to stable marriage

Simple item page
dc.contributor.authorGenc, Begum
dc.contributor.authorSiala, Mohamed
dc.contributor.authorSimonin, Gilles
dc.contributor.authorO'Sullivan, Barry
dc.contributor.editorSierra, Carles
dc.contributor.editorSierra, Carles
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2018-01-15T15:04:59Z
dc.date.available2018-01-15T15:04:59Z
dc.date.issued2017-08
dc.date.updated2018-01-15T14:56:37Z
dc.description.abstractWe 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.description.statusPeer revieweden
dc.description.versionPublished Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationGenc, 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/88en
dc.identifier.doi10.24963/ijcai.2017/88
dc.identifier.endpage637en
dc.identifier.isbn978-0-9992411-0-3
dc.identifier.journaltitleProceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)en
dc.identifier.startpage631en
dc.identifier.urihttps://hdl.handle.net/10468/5279
dc.language.isoenen
dc.publisherInternational Joint Conferences on Artificial Intelligence Organizationen
dc.relation.ispartofProceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.rights© 2017 International Joint Conferences on Artificial Intelligence All rights reserved.en
dc.subjectConstraintsen
dc.subjectSatisfiabilityen
dc.subjectKnowledge representationen
dc.subjectReasoning and logicen
dc.subjectPreferencesen
dc.subjectCombinatorial heuristic searchen
dc.subjectHeuristic searchen
dc.subjectAgent-based systemsen
dc.subjectMulti-agent systemsen
dc.subjectSocial choice theoryen
dc.titleFinding robust solutions to stable marriageen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
4583.pdf
Size:
202.83 KB
Format:
Adobe Portable Document Format
Description:
Published version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items