<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>9316</REFNUM><AUTHORS><AUTHOR>Biro,P.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>Mittal,S.</AUTHOR></AUTHORS><YEAR>2010</YEAR><TITLE>Size versus stability in the Marriage problem</TITLE><PLACE_PUBLISHED>Theoretical Computer Science, volume 411</PLACE_PUBLISHED><PUBLISHER>Elsevier Science</PUBLISHER><PAGES>1828-1841</PAGES><LABEL>Biro:2010:9316</LABEL><KEYWORDS><KEYWORD>Stable marriage problem; Stable matching; Blocking pair; Blocking agent; Inapproximability result; Polynomial-time algorithm</KEYWORD></KEYWORDS<ABSTRACT>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. We also
extend these results to the cases where (i) preference lists
may include ties, and (ii) we seek to minimise the number of
agents involved in a blocking pair.</ABSTRACT><URL>http://dx.doi.org/10.1016/j.tcs.2010.02.003</URL></RECORD></RECORDS></XML>