Constrainedness in stable matching

Show simple item record Escamocher, Guillaume O'Sullivan, Barry 2019-02-20T11:27:20Z 2019-02-20T11:27:20Z 2018-12-17
dc.identifier.citation Escamocher, G. and O'Sullivan, B. (2018) 'Constrainedness in stable matching', 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI), Volos, Greece, 5-7 November, pp. 710-717. doi:10.1109/ICTAI.2018.00112 en
dc.identifier.startpage 710 en
dc.identifier.endpage 717 en
dc.identifier.isbn 978-1-5386-7449-9
dc.identifier.isbn 978-1-5386-7450-5
dc.identifier.issn 2375-0197
dc.identifier.issn 1082-3409
dc.identifier.doi 10.1109/ICTAI.2018.00112
dc.description.abstract In constraint satisfaction problems, constrainedness provides a way to predict the number of solutions: for instances of a same size, the number of constraints is inversely correlated with the number of solutions. However, there is no obvious equivalent metric for stable matching problems. We introduce the contrarian score, a simple metric that is to matching problems what constrainedness is to constraint satisfaction problems. In addition to comparing the contrarian score against other potential tightness metrics, we test it for different instance sizes as well as extremely distinct versions of the stable matching problem. In all cases, we find that the correlation between contrarian score and number of solutions is very strong. en
dc.description.uri en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Institute of Electrical and Electronics Engineers (IEEE) en
dc.relation.ispartof 30th International Conference on Tools with Artificial Intelligence (ICTAI 2018)
dc.rights © 2018, IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. en
dc.subject Constraint handling en
dc.subject Constraint satisfaction problems en
dc.subject Contrarian score en
dc.subject Stable matching problem en
dc.subject Constrainedness en
dc.subject Matching problems en
dc.subject Tightness metrics en
dc.subject Measurement en
dc.subject Switches en
dc.subject Tools en
dc.subject Data analysis en
dc.subject Correlation en
dc.subject Conferences en
dc.subject Artificial intelligence en
dc.subject Stable matching en
dc.title Constrainedness in stable matching en
dc.type Conference item en
dc.internal.authorcontactother Guillaume Escamocher, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: en
dc.internal.availability Full text available en 2019-02-20T11:20:31Z
dc.description.version Accepted Version en
dc.internal.rssid 474293033
dc.contributor.funder Science Foundation Ireland en
dc.contributor.funder European Regional Development Fund en
dc.description.status Peer reviewed en
dc.internal.copyrightchecked Yes en
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Volos, Greece en
dc.internal.IRISemailaddress 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