Greedy Matchings
Rob Irving

Abstract:

There are many real-life situations in which applicants are to be matched 
to posts based on preferences expressed by one or both sides. When the 
preferences of both sides are to be taken into account, the key notion 
is that of a stable matching, and efficient algorithms are known, and are 
used in a variety of large-scale matching schemes, for a number of variants 
of the stable matching problem.

When preferences are on one side only - say only the applicants express 
preferences - a number of different criteria can be used to evaluate matchings. 
One possible notion of optimality in this context is that of a greedy matching, 
in which the maximum possible number of applicants are allocated their first 
choice post, and subject to that condition, the maximum possible number are 
allocated their second choice post, and so on. There is a well-established 
algorithm for the Greedy Matching problem based on a transformation to maximum 
weight bipartite matching. However, the transformation involves integers of 
exponentially growing size, which adversely affects the complexity and the 
practicality of the resulting algorithm.

Here, we describe a more direct and more practical algorithm for Greedy Matching, 
based on an appropriate notion of augmenting path in an alternative weighted 
bipartite graph representation.