Computing at Glasgow University
Paper ID: 9378

Improving man-optimal stable matchings by minimum change of preference lists
Inoshita,T. Irving,R.W. Iwama,K. Miyazaki,S. Nagase,T.

Publication Type: Conference Proceedings
Appeared in: Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (Kyoto, Japan)
Page Numbers : 309-313
Publisher: N/A
Year: 2011

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.

Keywords: stable marriage problem, man-optimal stable matching

Bibtex entry Endnote XML