New models for two variants of popular matching
Loading...
Files
Accepted version
Date
2017
Authors
Chisca, Danuta Sorina
Siala, Mohamed
Simonin, Gilles
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
Published Version
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 M0 where more applicants prefer M0 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.
Description
Keywords
Computer programming , Computer science , Matching under preferences , Real-world applications , Popular matching
Citation
Chisca, D. S., Siala, M., Simonin, G. and O'Sullivan, B. (2017) New Models for Two Variants of Popular Matching ICTAI 2017: The annual IEEE International Conference on Tools with Artificial Intelligence, Boston, MA, USA, 06 - 09 November, publication forthcoming.
Link to publisher’s version
Copyright
Publication forthcoming © 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.