Constrainedness in stable matching

Simple item page
dc.contributor.authorEscamocher, Guillaume
dc.contributor.authorO'Sullivan, Barry
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderEuropean Regional Development Funden
dc.date.accessioned2019-02-20T11:27:20Z
dc.date.available2019-02-20T11:27:20Z
dc.date.issued2018-12-17
dc.date.updated2019-02-20T11:20:31Z
dc.description.abstractIn 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.statusPeer revieweden
dc.description.urihttp://ictai2018.org/en
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationEscamocher, 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.00112en
dc.identifier.doi10.1109/ICTAI.2018.00112
dc.identifier.endpage717en
dc.identifier.isbn978-1-5386-7449-9
dc.identifier.isbn978-1-5386-7450-5
dc.identifier.issn2375-0197
dc.identifier.issn1082-3409
dc.identifier.startpage710en
dc.identifier.urihttps://hdl.handle.net/10468/7526
dc.language.isoenen
dc.publisherInstitute of Electrical and Electronics Engineers (IEEE)en
dc.relation.ispartof30th International Conference on Tools with Artificial Intelligence (ICTAI 2018)
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://ieeexplore.ieee.org/document/8576110
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.subjectConstraint handlingen
dc.subjectConstraint satisfaction problemsen
dc.subjectContrarian scoreen
dc.subjectStable matching problemen
dc.subjectConstrainednessen
dc.subjectMatching problemsen
dc.subjectTightness metricsen
dc.subjectMeasurementen
dc.subjectSwitchesen
dc.subjectToolsen
dc.subjectData analysisen
dc.subjectCorrelationen
dc.subjectConferencesen
dc.subjectArtificial intelligenceen
dc.subjectStable matchingen
dc.titleConstrainedness in stable matchingen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Constrainedness_in_Stable_Matching.pdf
Size:
288.71 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
Insight Centre for Data Analytics - Conference Items
Computer Science - Conference Items