论文标题
最大匹配和受欢迎程度
Maximum Matchings and Popularity
论文作者
论文摘要
令$ g $为双方图，每个节点都有严格的邻居排名。对于每个节点，其对邻居的偏好自然而然地扩展到匹配的偏好。如果比$ m $匹配的$ n $比匹配$ m $更受欢迎。如果$ g $中没有最大匹配，则最大匹配的$ m $是“流行的最大匹配”，它比$ m $更受欢迎。此类匹配在应用程序集是一组最大匹配的应用中相关，我们希望根据节点首选项找到最佳的最大匹配。众所周知，流行的最大匹配始终以$ g $存在。在这里，我们为流行的最大匹配多层室展示了紧凑的扩展配方。因此，当有优势成本时，可以在多项式时间内计算出最小成本的流行最大匹配。这与已知NP-HARD的最小成本流行匹配问题相反。我们还考虑了帕累托式挑剔，这是一种普遍性的放松，并表明计算最小成本的帕累托最佳匹配/最大匹配是NP-HARD。
Let $G$ be a bipartite graph where every node has a strict ranking of its neighbors. For every node, its preferences over neighbors extend naturally to preferences over matchings. Matching $N$ is more popular than matching $M$ if the number of nodes that prefer $N$ to $M$ is more than the number that prefer $M$ to $N$. A maximum matching $M$ in $G$ is a "popular max-matching" if there is no maximum matching in $G$ that is more popular than $M$. Such matchings are relevant in applications where the set of admissible solutions is the set of maximum matchings and we wish to find a best maximum matching as per node preferences. It is known that a popular max-matching always exists in $G$. Here we show a compact extended formulation for the popular max-matching polytope. So when there are edge costs, a min-cost popular max-matching in $G$ can be computed in polynomial time. This is in contrast to the min-cost popular matching problem which is known to be NP-hard. We also consider Pareto-optimality, which is a relaxation of popularity, and show that computing a min-cost Pareto-optimal matching/max-matching is NP-hard.
