TY - GEN
T1 - New models for two variants of popular matching
AU - Chisca, Danuta Sorina
AU - Siala, Mohamed
AU - Simonin, Gilles
AU - O'Sullivan, Barry
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/7/2
Y1 - 2017/7/2
N2 - 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. In this paper we address the case involving ties and propose novel algorithmic and complexity results for 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.
AB - 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. In this paper we address the case involving ties and propose novel algorithmic and complexity results for 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.
KW - Branching strategies
KW - Popular Matching
KW - Preferences
UR - https://www.scopus.com/pages/publications/85048463761
U2 - 10.1109/ICTAI.2017.00119
DO - 10.1109/ICTAI.2017.00119
M3 - Conference proceeding
AN - SCOPUS:85048463761
T3 - Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI
SP - 752
EP - 759
BT - Proceedings - 2017 International Conference on Tools with Artificial Intelligence, ICTAI 2017
PB - IEEE Computer Society
T2 - 29th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2017
Y2 - 6 November 2017 through 8 November 2017
ER -