New models for two variants of popular matching

Show simple item record Chisca, Danuta Sorina Siala, Mohamed Simonin, Gilles O'Sullivan, Barry 2018-01-16T15:10:16Z 2018-01-16T15:10:16Z 2017
dc.identifier.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. en
dc.identifier.startpage 1 en
dc.identifier.endpage 8 en
dc.description.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. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher IEEE en
dc.relation.ispartof ICTAI 2017: The annual IEEE International Conference on Tools with Artificial Intelligence
dc.rights 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. en
dc.subject Computer programming en
dc.subject Computer science en
dc.subject Matching under preferences en
dc.subject Real-world applications en
dc.subject Popular matching en
dc.title New models for two variants of popular matching en
dc.type Conference item en
dc.internal.authorcontactother Mohamed Siala, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: en
dc.internal.availability Full text available en 2018-01-16T14:59:26Z
dc.description.version Accepted Version en
dc.internal.rssid 422048004
dc.contributor.funder Science Foundation Ireland en
dc.description.status Peer reviewed en
dc.identifier.journaltitle ICTAI 2017: The annual IEEE International Conference on Tools with Artificial Intelligence en
dc.internal.copyrightchecked No !!CORA!! 5. IEEE does not restrict the rights of authors to use their IEEE-copyrighted articles in their own teaching, training, or work responsibilities, or those of their institutions or employers. In any preprint version archived by the author after submission, IEEE requires that IEEE will be credited as copyright holder. Upon publication of the work, authors are asked to include the article’s Digital Object Identifier (DOI). [ ] en
dc.internal.licenseacceptance Yes en
dc.internal.conferencelocation Boston, MA, USA en
dc.internal.IRISemailaddress en
dc.relation.project info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ en

Files in this item

This item appears in the following Collection(s)

Show simple item record

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement