Rank-maximal matchings

ABSTRACT

Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A greedy matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [8].We define the bipartite graph G = (A U P,ε), where ε consists of all pairs (a, p) such that post p appears in the preference list of applicant a. Each edge (a, p) has a rank i, which means that post p is an ith choice for applicant a. The traditional solution of computing a greedy matching in G would be to use the Hungarian algorithm to compute a maximum weight matching by assigning a suitably steeply decreasing sequence of weights to the edges. This would result in an algorithm with worst case running time rn(m + n log n) and the space requirement Θ(rm), where n is the number of vertices, m is the number of edges and r is the largest rank of an edge.Here, we describe two algorithms to compute a greedy matching that improve upon this algorithm. We give a combinatorial algorithm with running time O(min(n + C,C√n)m), where C ≤ r is the maximal rank of an edge used in a greedy matching. This algorithm works in phases and uses the maximum cardinality matching algorithm. We also give an O(Cnm) algorithm that tackles the problem of large edge weights introduced by the Hungarian algorithm. This algorithm uses scaling and works in phases. The space requirement of both these algorithms is O(m).

REFERENCES

• 1: H. N. Gabow , R. E. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing, v.18 n.5, p.1013-1036, Oct. 1989 [doi>10.1137/0218069]
• 2: D. Gale and L. S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9--15, 1962.
• 3: R. L. Graham , M. Grötschel , L. Lovász, Handbook of combinatorics (vol. 1), MIT Press, Cambridge, MA, 1996
• 4: Dan Gusfield , Robert W. Irving, The stable marriage problem: structure and algorithms, MIT Press, Cambridge, MA, 1989
• 5: M. M. Halldórsson, K. Iwama, S. Miyasaki, and H. Yanagisawa. Improved approximation of the stable marriage problem. to appear in ESA 2003.
• 6: J. E. Hopcroft and R. M. Karp. An n5/2 algorithm for maximum matching in bipartite graphs. SIAM Journal on Computing, 2:225--231, 1973.
• 7: Robert W. Irving, Matching Medical Students to Pairs of Hospitals: A New Variation on a Well-Known Theme, Proceedings of the 6th Annual European Symposium on Algorithms, p.381-392, August 24-26, 1998
• 8: R. W. Irving. Greedy matchings. Technical Report TR-2003-136, University of Glasgow, April 2003.
• 9: Robert W. Irving , David Manlove , Sandy Scott, Strong Stability in the Hospitals/Residents Problem, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.439-450, February 27-March 01, 2003
• 10: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 11: James B. Orlin , Ravindra K. Ahuja, New scaling algorithms for the assignment and minimum mean cycle problems, Mathematical Programming: Series A and B, v.54 n.1, p.41-56, Feb. 17, 1992 [doi>10.1007/BF01586040]
• 12: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 13: A. E. Roth. The evaluation of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, 92(6), 1984.