Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, June 30, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Florin Oswald
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 M2 such that the number of applicants preferring M2 to M exceeds the number of applicants preferring M to M2. 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(√n m) time algorithm, and show that the problem has equivalent time complexity to the maximum-cardinality bipartite matching problem.
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Popular matchings, SODA 2005, 424- 432.
Automatic MiSe System Software Version 1.4803M | admin login