You are here

New Models for Two Variants of Popular Matching

Authors: 

Sorina Chisca, Mohamed Siala, Gilles Simonin,, Barry O'Sullivan,

Publication Type: 
Refereed Original Article
Abstract: 
We study the problem of matching a set of applicants to a set of posts, where each applicant has an ordinal preference list, which may contain ties, ranking a subset of posts. A matching M is popular if there exists no matching M′ where more applicants prefer M ′ to M . Several notions of optimality are studied in the literature for the case of strictly ordered preference lists. We fill the gap in this paper for the case involving ties and propose novel algorithmic and complexity results to this variant. Next, we focus on the NP-Hard case where additional copies of posts can be added in the preference lists, called Popular Matching with Copies. We define new dominance rules for this problem and present several novel graph properties characterising the posts that should be copied with priority. We present a comprehensive set of experiments for the popular matching problem with copies to evaluate our dominance rules as well as the different branching strategies. Our experimental study emphasizes the importance of the dominance rules and characterises the key aspects of a good branching strategy.
Digital Object Identifer (DOI): 
NOT YET
Publication Status: 
In Press
Date Accepted for Publication: 
Saturday, 2 September, 2017
Publication Date: 
04/11/2017
Journal: 
The annual IEEE International Conference on Tools with Artificial Intelligence (ICTAI)
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No
Publication document: