Let G = (A U P, E) be a bipartite graph where A denotes a set of agents, Pdenotes a set of posts and ranks on the edges denote preferences of the agentsover posts. A matching M in G is rank-maximal if it matches the maximum numberof applicants to their top-rank post, subject to this, the maximum number ofapplicants to their second rank post and so on. In this paper, we develop a switching graph characterization of rank-maximalmatchings, which is a useful tool that encodes all rank-maximal matchings in aninstance. The characterization leads to simple and efficient algorithms forseveral interesting problems. In particular, we give an efficient algorithm tocompute the set of rank-maximal pairs in an instance. We show that the problemof counting the number of rank-maximal matchings is #P-Complete and also givean FPRAS for the problem. Finally, we consider the problem of deciding whethera rank-maximal matching is popular among all the rank-maximal matchings in agiven instance, and give an efficient algorithm for the problem.
展开▼
机译：令G =（A U P，E）是二部图，其中A表示一组座席，P表示一组座席，其边上的等级表示座席相对于座席的偏好。如果G中匹配的M与排名最高的职位的最大申请人数相匹配（在此基础上，与排名第二的职位的最大申请人数相匹配），则M为最高排名。在本文中，我们开发了秩最大匹配的切换图特征，这是对实例中所有秩最大匹配进行编码的有用工具。表征导致针对几个有趣问题的简单有效算法。特别是，我们提供了一种有效的算法来计算实例中的秩最大对的集合。我们表明，计算秩最大匹配数的问题是＃P-Complete，并且给出了该问题的FPRAS。最后，我们考虑确定给定实例中的所有秩最大匹配中是否普遍采用秩最大匹配的问题，并给出了解决该问题的有效算法。
展开▼
