New Models for Two Variants of Popular Matching
Refereed Conference Meeting Proceeding
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.
The annual IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2017
Digital Object Identifer (DOI):
National University of Ireland, Cork (UCC)
Open access repository: