Computing at Glasgow University
Paper ID: 9113

Size versus stability in the Marriage problem
Biro,P. Manlove,D.F. Mittal,S.

Publication Type: Conference Proceedings
Appeared in: Proceedings of WAOA 2008: the 6th Workshop on Approximation and Online Algorithms, volume 5426 of Lecture Notes in Computer Science
Page Numbers : 15-28
Publisher: Springer
Year: 2009

URL: This publication is available at this URL.


Given an instance I of the classical Stable Marriage problem with Incomplete preference lists (SMI), a maximum cardinality matching can be larger than a stable matching. In many large-scale applications of SMI, we seek to match as many agents as possible. This motivates the problem of finding a maximum cardinality matching in I that admits the smallest number of blocking pairs (so is "as stable as possible"). We show that this problem is NP-hard and not approximable within n^{1-\varepsilon}, for any \varepsilon>0, unless P=NP, where n is the number of men in I. Further, even if all preference lists are of length at most 3, we show that the problem remains NP-hard and not approximable within \delta, for some \delta>1. By contrast, we give a polynomial-time algorithm for the case where the preference lists of one sex are of length at most 2.

PDF Bibtex entry Endnote XML