You are here

Constraint Programming models for stable and popular matchings

Sorina's Abstract: The popular matching problem involves finding a matching M between applicants and posts such that there exists no matching M’ where more applicants prefer M’ to M.We propose the first constraint programming approach to solve this problem. Then we tackle the more general case where additional copies of posts can be made in order to find a popular matching. We introduce new graph properties characterising the posts that should be copied first. Next, we design a simple filtering rule. Our experimental results show the utility of our approach for solving variants of the popular matching problem. Mohamed's Abstract: We show that previous filtering propositions on two-sided stability problems do not enforce arc consistency (AC), however they maintain Bound(D) Consistency (BC(D)). We propose an optimal algorithm achieving BC(D) with O(L) time complexity where L is the length of the preference lists. We also show an adaptation of this filtering approach to achieve AC. Next, we report the first polynomial time algorithm for solving the hospital/resident problem with forced and forbidden pairs. Furthermore, we show that the particular case of this problem for stable marriage can be solved in O(n^2 ) which improves the previously best complexity by a factor of n^2 . Finally, we present a comprehensive set of experiments to evaluate the filtering propositions
Speaker Name: 
Danuta Sorina Chisca and Mohamed Siala
Speaker Bio: 
PhD student and PostDoctoral Researcher at Insight Centre for Data Analytics - UCC
Speaker Photo: 
Seminar Date: 
Wednesday, 18 May, 2016 (All day)
Seminar Location: 
WGB 2.16