<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>9378</REFNUM><AUTHORS><AUTHOR>Inoshita,T.</AUTHOR><AUTHOR>Irving,R.W.</AUTHOR><AUTHOR>Iwama,K.</AUTHOR><AUTHOR>Miyazaki,S.</AUTHOR><AUTHOR>Nagase,T.</AUTHOR></AUTHORS><YEAR>2011</YEAR><TITLE>Improving man-optimal stable matchings by minimum change of preference lists</TITLE><PLACE_PUBLISHED>Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (Kyoto, Japan)</PLACE_PUBLISHED><PUBLISHER>N/A</PUBLISHER><PAGES>309-313</PAGES><LABEL>Inoshita:2011:9378</LABEL><KEYWORDS><KEYWORD>stable marriage problem</KEYWORD></KEYWORDS<ABSTRACT>In the stable marriage problem, any instance admits so-called the 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.</ABSTRACT></RECORD></RECORDS></XML>