Reducing rank-maximal to maximum weight matching
Given a bipartite graph G(V, E), V = A(boolean OR) over dot where vertical bar V vertical bar = n, vertical bar E vertical bar = m and a partition of the edge set into r <= m disjoint subsets E = E-1(boolean OR) over dot E-2(boolean OR) over dot ... (boolean OR) over dot E-r, which are called ranks, the rank-maximal matching problem is to find a matching M of G such that vertical bar M boolean AND E-1 vertical bar is maximized and given that vertical bar M boolean AND E-1 vertical bar is maximized, vertical bar M boolean AND E-2 vertical bar is also maximized, and so on. Such a problem arises as an optimization criteria over a possible assignment of a set of applicants to a set of posts. The matching represents the assignment and the ranks on the edges correspond to a ranking of the posts submitted by the applicants. The rank-maximal matching problem and several other optimization variants, e.g. fair matching and maximum cardinality rank-maximal matching, can be solved by a reduction to the weight matching problem in time O (r root nm log n). Recently, Irving et al. developed a combinatorial approach which improves the running time for the rank-maximal matching problem to O (min (n + r, r root n)m). They raised the open questions on (a) whether such a running time can be achieved by the weight matching reduction and (b) whether such a running time can be achieved for the other variants of the problem. In this work we show how the reduction to the weight matching problem can also be used to achieve the same running time. Our algorithm is simpler and more intuitive. (c) 2007 Elsevier B.V All rights reserved.
rank-maximal weighted matching matching bipartite graph preference lists