文章基本信息

标题：MANY-TO-MANY STABLE MATCHINGS WITH TIES IN TREES
本地全文：下载
作者：Keita Nakamura ; Naoyuki Kamiyama
期刊名称：日本オペレーションズ・リサーチ学会論文誌
印刷版ISSN：0453-4514
电子版ISSN：2188-8299
出版年度：2016
卷号：59
期号：3
页码：225-240
DOI：10.15807/jorsj.59.225
出版社：Japan Science and Technology Information Aggregator, Electronic
摘要：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.
关键词：Discrete optimization;stable matching;tree;tie