We consider capacitated rank-maximal matchings. Rankmaximal matchings have been considered before and are defined as follows. We are given a bipartite graph G = (A ∪ P, E), in which A denotes applicants, P posts and edges have ranks – an edge (a, p) has rank i if p belongs to (one of) a's ith choices. A matching M is called rank-maximal if the largest possible number of applicants is matched in M to their first choice posts and subject to this condition the largest number of appplicants is matched to their second choice posts and so on. We give a combinatorial algorithm for the capacitated version of the rank-maximal matching problem, in which each applicant or post v has capacity b(v). The algorithm runs in O(min(B,C√B)m) time, where C is the maximal rank of an edge in an optimal solution and B = min(∑_(a∈A) b(a),∑_(p∈P) b(p)) and n,m denote the number of vertices/edges respectively. (B depends on the graph, however it never exceeds m.) The previously known algorithm [11] for this problem has a worse running time of O(Cnmlog(n~2/m) log n) and is not combinatorial –it is based on a weakly polynomial algorithm of Gabow and Tarjan using scaling. To construct the algorithm we use the generalized Gallai-Edmonds decomposition theorem, which we prove in a convenient form for our purposes. As a by-product we obtain a faster (by a factor of O(√n)) algorithm for the Capacitated House Allocation with Ties problem.
展开▼
