Computing at Glasgow University
Paper ID: 8904
DCS Tech Report Number: TR-2008-283

Size Versus Stability in the Marriage Problem
Biro,P. Manlove,D.F. Mittal,S.

Publication Type: Tech Report (internal)
Appeared in: DCS Technical Report Series
Page Numbers :
Publisher: Dept of Computing Science, University of Glasgow
Year: 2008

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