Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists†

Algorithms

Takao Inoshita¹  Robert W. Irving²  Kazuo Iwama¹  Shuichi Miyazaki³ 

[1] Graduate School of Informatics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501, Japan; E-Mails:;School of Computing Science, University of Glasgow, Glasgow, G12 8QQ, Scotland; E-Mail:;Academic Center for Computing and Media Studies, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501, Japan

关键词: combinatorial optimization;    polynomial-time algorithms;    stable marriage problem;    man-optimal stable matching;   

DOI  :  10.3390/a6020371

来源: mdpi

【 摘 要 】

In the stable marriage problem, any instance admits the so-called man-optimal stable matching, in which every man is assigned the best possible partner. However, there are instances for which all men receive low-ranked partners even in the man-optimal stable matching. In this paper we consider the problem of improving the man-optimal stable matching by changing only one man’s preference list. We show that the optimization variant and the decision variant of this problem can be solved in time -time algorithms for the optimization and decision variants, respectively.

【 授权许可】

CC BY   
© 2013 by the authors; licensee MDPI, Basel, Switzerland.