Three-dimensional matching instances are rich in stable matchings

Simple item page
dc.contributor.authorEscamocher, Guillaume
dc.contributor.authorO'Sullivan, Barry
dc.contributor.editorvan Hoeve, W. J.
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2018-08-21T16:02:13Z
dc.date.available2018-08-21T16:02:13Z
dc.date.issued2018-06-09
dc.date.updated2018-08-21T15:53:14Z
dc.description.abstractExtensive 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.sponsorshipGrant Number SFI/12/RC/2289.en
dc.description.statusPeer revieweden
dc.description.urihttps://link.springer.com/conference/cpaioren
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationEscamocher 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_13en
dc.identifier.doi10.1007/978-3-319-93031-2_13
dc.identifier.endpage197en
dc.identifier.issn0302-9743
dc.identifier.issn978-3-319-93031-2
dc.identifier.issn978-3-319-93030-5
dc.identifier.journaltitleLecture Notes in Computer Scienceen
dc.identifier.startpage182en
dc.identifier.urihttps://hdl.handle.net/10468/6633
dc.identifier.volume10848en
dc.language.isoenen
dc.publisherSpringer Verlagen
dc.relation.ispartofCPAIOR 2018: International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.projectSFI/12/RC/2289en
dc.relation.urihttps://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_13en
dc.subjectArtificial intelligenceen
dc.subjectEmpirical experimentsen
dc.subjectExponential numbersen
dc.subjectPreference listsen
dc.subjectSet extensionen
dc.subjectShow throughen
dc.subjectStable matchingen
dc.subjectStable matching problemen
dc.subjectThree dimensional matchingen
dc.subjectComputer programmingen
dc.subjectConstraint theoryen
dc.subjectOperations researchen
dc.titleThree-dimensional matching instances are rich in stable matchingsen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
5962_three-dimensional-matching.pdf
Size:
285.51 KB
Format:
Adobe Portable Document Format
Description:
Accepted 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