Conference Publication Details
Mandatory Fields
Escamocher, Guillaume; O'Sullivan, Barry
30th International Conference on Tools with Artificial Intelligence (ICTAI 2018)
Constrainedness in stable matching
2018
November
Validated
0
()
Optional Fields
Constraint handling Constraint satisfaction problems Contrarian score Stable matching problem Constrainedness Matching problems Tightness metrics Measurement Switches Tools Data analysis Correlation Conferences Artificial intelligence Stable matching
710
717
Volos, Greece
05-NOV-18
07-NOV-18
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.
https://ieeexplore.ieee.org/document/8576110
10.1109/ICTAI.2018.00112
Grant Details