UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 9166

Popular matchings: structure and algorithms
McDermid,E. Irving,R.W.

Publication Type: Conference Proceedings
Appeared in: Proceedings of COCOON 2009, 15th Annual International Computing and Combinatorics Conference, Niagara Falls USA, July 2009, Lecture Notes in Computer Science vol. 5609
Page Numbers : 506-515
Publisher: Springer
Year: 2009
ISBN/ISSN:
Abstract:

An instance of the popular matching problem (POP-M) consists of a set of applicants and a set of posts. Each applicant has a preference list that strictly ranks a subset of the posts. A matching M of applicants to posts is popular if there is no other matching M' such that more applicants prefer M' to M than prefer M to M'. This paper provides a characterization of the set of popular matchings for an arbitrary POP-M instance in terms of a structure called the switching graph, a directed graph computable in linear time from the preference lists. We show that the switching graph can be exploited to yield efficient algorithms for a range of associated problems, including the counting and enumeration of the set of popular matchings and computing popular matchings that satisfy various additional optimality criteria. Our algorithms for computing such optimal popular matchings improve those described in a recent paper by Kavitha and Nasre.

Keywords: Matching, efficient algorithms


PDF Bibtex entry Endnote XML