All Title Author
Keywords Abstract

Publish in OALib Journal
ISSN: 2333-9721
APC: Only $99


Relative Articles

Algorithms  2013 

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

DOI: 10.3390/a6020371

Keywords: combinatorial optimization, polynomial-time algorithms, stable marriage problem, man-optimal stable matching

Full-Text   Cite this paper   Add to My Lib


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.


comments powered by Disqus

Contact Us


WhatsApp +8615387084133

WeChat 1538708413