<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>8590</REFNUM><AUTHORS><AUTHOR>Abraham,D.J.</AUTHOR><AUTHOR>Irving,R.W.</AUTHOR><AUTHOR>Kavitha,T.</AUTHOR><AUTHOR>Mehlhorn,K.</AUTHOR></AUTHORS><YEAR>2007</YEAR><TITLE>Popular Matchings</TITLE><PLACE_PUBLISHED>SIAM Journal on Computing, Volume 37</PLACE_PUBLISHED><PUBLISHER>Society for Industrial and Applied Mathematics</PUBLISHER><PAGES>1030 - 1045</PAGES><LABEL>Abraham:2007:8590</LABEL><KEYWORDS><KEYWORD>Matching</KEYWORD></KEYWORDS<ABSTRACT>We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in order of preference, possibly involving ties.
We say that a matching M is popular if there is no matching M' such that the number of applicants preferring M' to M exceeds the number of applicants preferring M to M'.
In this paper, we give the first polynomial-time algorithms to determine if an instance admits a popular matching, and to find a largest such matching, if one exists.
For the special case in which every preference list is strictly ordered (i.e. contains no ties), we give an O(n + m) time algorithm, where n is the total number of applicants and posts, and m is the total length of all the preference lists.
For the general case in which preference lists may contain ties, we give an O(\sqrt{n}m) time algorithm, and show that the problem has equivalent time complexity to the maximum-cardinality bipartite matching problem.</ABSTRACT></RECORD></RECORDS></XML>