Computing relaxations for the three-dimensional stable matching problem with cyclic preferences

Simple item page
dc.contributor.authorCseh, Ágnes
dc.contributor.authorEscamocher, Guillaume
dc.contributor.authorQuesada, Luis
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderEuropean Regional Development Funden
dc.contributor.funderHungarian Scientific Research Funden
dc.contributor.funderMagyar Tudományos Akadémiaen
dc.date.accessioned2022-07-27T14:21:46Z
dc.date.available2022-07-27T14:21:46Z
dc.date.issued2022-07-23
dc.date.updated2022-07-27T14:07:43Z
dc.description.abstractConstraint programming has proven to be a successful framework for determining whether a given instance of the three-dimensional stable matching problem with cyclic preferences (3dsm-cyc) admits a solution. If such an instance is satisfiable, constraint models can even compute its optimal solution for several different objective functions. On the other hand, the only existing output for unsatisfiable 3dsm-cyc instances is a simple declaration of impossibility. In this paper, we explore four ways to adapt constraint models designed for 3dsm-cyc to the maximum relaxation version of the problem, that is, the computation of the smallest part of an instance whose modification leads to satisfiability. We also extend our models to support the presence of costs on elements in the instance, and to return the relaxation with lowest total cost for each of the four types of relaxation. Empirical results reveal that our relaxation models are efficient, as in most cases, they show little overhead compared to the satisfaction version.en
dc.description.sponsorshipScience Foundation Ireland (Grant numbers 12/RC/2289-P2 and 16/SP/3804, co-funded under the European Regional Development Fund); Hungarian Scientific Research Fund (OTKA grant K128611; Magyar Tudományos Akadémia, Hungarian Academy of Sciences (János Bolyai Research Fellowship)en
dc.description.statusPeer revieweden
dc.description.versionPublished Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.articleid16en
dc.identifier.citationCseh, Á., Escamocher, G. and Quesada, L. (2022) 'Computing Relaxations for the Three-Dimensional Stable Matching Problem with Cyclic Preferences', CP 2022: 28th International Conference on Principles and Practice of Constraint Programming Haifa, Israel, 31 July-5 August. 16:1-16:19. doi: 10.4230/LIPIcs.CP.2022.16en
dc.identifier.doi10.4230/LIPIcs.CP.2022.16en
dc.identifier.endpage19en
dc.identifier.isbn978-3-95977-240-2
dc.identifier.issn1868-8969
dc.identifier.startpage1en
dc.identifier.urihttps://hdl.handle.net/10468/13413
dc.identifier.volume235en
dc.language.isoenen
dc.publisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik GmbHen
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.urihttps://doi.org/10.4230/LIPIcs.CP.2022.16
dc.relation.urihttps://drops.dagstuhl.de/opus/volltexte/2022/16645
dc.rights© Ágnes Cseh, Guillaume Escamocher, and Luis Quesada; licensed under Creative Commons License CC-BY 4.0en
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subjectThree-dimensional stable matching with cyclic preferencesen
dc.subject3dsm-cycen
dc.subjectConstraint Programmingen
dc.subjectRelaxationen
dc.subjectAlmost stable matchingen
dc.titleComputing relaxations for the three-dimensional stable matching problem with cyclic preferencesen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LIPIcs-CP-2022-16.pdf
Size:
1.04 MB
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