New models for two variants of popular matching

Simple item page
dc.contributor.authorChisca, Danuta Sorina
dc.contributor.authorSiala, Mohamed
dc.contributor.authorSimonin, Gilles
dc.contributor.authorO'Sullivan, Barry
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2018-01-16T15:10:16Z
dc.date.available2018-01-16T15:10:16Z
dc.date.issued2017
dc.date.updated2018-01-16T14:59:26Z
dc.description.abstractWe 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.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationChisca, D.S., Siala, M., Simonin, G. and O’Sullivan, B. (2017) ‘New models for two variants of popular matching’, in 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI). Boston, MA: IEEE, pp. 752–759. Available at: https://doi.org/10.1109/ICTAI.2017.00119.en
dc.identifier.doihttps://doi.org/10.1109/ICTAI.2017.00119en
dc.identifier.endpage8en
dc.identifier.journaltitleICTAI 2017: The annual IEEE International Conference on Tools with Artificial Intelligenceen
dc.identifier.startpage1en
dc.identifier.urihttps://hdl.handle.net/10468/5284
dc.language.isoenen
dc.publisherIEEEen
dc.relation.ispartofICTAI 2017: The annual IEEE International Conference on Tools with Artificial Intelligence
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.rights© 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.subjectComputer programmingen
dc.subjectComputer scienceen
dc.subjectMatching under preferencesen
dc.subjectReal-world applicationsen
dc.subjectPopular matchingen
dc.titleNew models for two variants of popular matchingen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
4616.pdf
Size:
449.73 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items