%0 Journal Article
%T Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists
%A Takao Inoshita
%A Robert W. Irving
%A Kazuo Iwama
%A Shuichi Miyazaki
%A Takashi Nagase
%J Algorithms
%D 2013
%I MDPI AG
%R 10.3390/a6020371
%X 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 O( n 3) and O( n 2), respectively, where n is the number of men (women) in an input. We further extend the problem so that we are allowed to change k men¡¯s preference lists. We show that the problem is W[1]-hard with respect to the parameter k and give O( n 2k+1)-time and O( n k+1)-time exact algorithms for the optimization and decision variants, respectively. Finally, we show that the problems become easy when k = n; we give O( n2.5 log n)-time and O( n 2)-time algorithms for the optimization and decision variants, respectively.
%K combinatorial optimization
%K polynomial-time algorithms
%K stable marriage problem
%K man-optimal stable matching
%U http://www.mdpi.com/1999-4893/6/2/371