MANY-TO-MANY STABLE MATCHINGS WITH TIES IN TREES

MANY-TO-MANY STABLE MATCHINGS WITH TIES IN TREES
复制标题

树中具有关系的多对多稳定匹配

DOI：
10.15807/jorsj.59.225
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Naoyuki Kamiyama
Naoyuki Kamiyama
中科院分区：
--
文献类型：
--
作者：
Keita Nakamura;Naoyuki Kamiyama

文献摘要

被引文献

相似文献

在Gale和Shapley引入的稳定匹配问题中，已知在偏好列表可能涉及领带的情况下，稳定匹配总是存在的，但是稳定匹配的大小可能不同。本文研究了在多对多匹配市场中寻找最大规模稳定匹配的问题。即使每个代理的容量都是1，该问题也是NP难的。在本文中，我们证明了这个问题在树上可以解决多项式时间内由Tayu和Ueno提出的一对一设置的算法。
In the stable matching problem introduced by Gale and Shapley, it is known that in the case where the preference lists may involve ties, a stable matching always exists, but the sizes of stable matchings may be different. In this paper, we consider the problem of finding a maximum-size stable matching in a many-to-many matching market with ties. It is known that this problem is NP-hard even if the capacity of every agent is one. In this paper, we prove that this problem in trees can be solved in polynomial time by extending the algorithm proposed by Tayu and Ueno for the one-to-one setting.