Three-dimensional matching instances are rich in stable matchings

Show simple item record

dc.contributor.author Escamocher, Guillaume
dc.contributor.author O'Sullivan, Barry
dc.contributor.editor van Hoeve, W. J.
dc.date.accessioned 2018-08-21T16:02:13Z
dc.date.available 2018-08-21T16:02:13Z
dc.date.issued 2018-06-09
dc.identifier.citation Escamocher G., O’Sullivan B. (2018) Three-Dimensional Matching Instances Are Rich in Stable Matchings. In: van Hoeve WJ. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2018, Delft, Netherlands, 26-29 June, Lecture Notes in Computer Science, vol 10848. Springer, Cham, pp. 182-197. doi: 10.1007/978-3-319-93031-2_13 en
dc.identifier.volume 10848 en
dc.identifier.startpage 182 en
dc.identifier.endpage 197 en
dc.identifier.issn 0302-9743
dc.identifier.issn 978-3-319-93031-2
dc.identifier.issn 978-3-319-93030-5
dc.identifier.uri http://hdl.handle.net/10468/6633
dc.identifier.doi 10.1007/978-3-319-93031-2_13
dc.description.abstract Extensive studies have been carried out on the Stable Matching problem, but they mostly consider cases where the agents to match belong to either one or two sets. Little work has been done on the three-set extension, despite the many applications in which three-dimensional stable matching (3DSM) can be used. In this paper we study the Cyclic 3DSM problem, a variant of 3DSM where agents in each set only rank the agents from one other set, in a cyclical manner. The question of whether every Cyclic 3DSM instance admits a stable matching has remained open for many years. We give the exact number of stable matchings for the class of Cyclic 3DSM instances where all agents in the same set share the same master preference list. This number is exponential in the size of the instances. We also show through empirical experiments that this particular class contains the most constrained Cyclic 3DSM instances, the ones with the fewest stable matchings. This would suggest that not only do all Cyclic 3DSM instances have at least one stable matching, but they each have an exponential number of them. en
dc.description.sponsorship Grant Number SFI/12/RC/2289. en
dc.description.uri https://link.springer.com/conference/cpaior en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Springer Verlag en
dc.relation.ispartof CPAIOR 2018: International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations
dc.relation.uri https://doi.org/10.1007/978-3-319-93031-2_13
dc.rights © Springer International Publishing AG, part of Springer Nature 2018. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-319-93031-2_13 en
dc.subject Artificial intelligence en
dc.subject Empirical experiments en
dc.subject Exponential numbers en
dc.subject Preference lists en
dc.subject Set extension en
dc.subject Show through en
dc.subject Stable matching en
dc.subject Stable matching problem en
dc.subject Three dimensional matching en
dc.subject Computer programming en
dc.subject Constraint theory en
dc.subject Operations research en
dc.title Three-dimensional matching instances are rich in stable matchings en
dc.type Conference item en
dc.internal.authorcontactother Guillaume Escamocher, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: guillaume.escamocher@insight-centre.org en
dc.internal.availability Full text available en
dc.check.info Access to this article is restricted until 12 months after publication by request of the publisher. en
dc.check.date 2019-06-09
dc.date.updated 2018-08-21T15:53:14Z
dc.description.version Accepted Version en
dc.internal.rssid 450401235
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle Lecture Notes in Computer Science en
dc.internal.copyrightchecked No !!CORA!! en
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Delft, Netherlands en
dc.internal.IRISemailaddress guillaume.escamocher@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