<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>9113</REFNUM><AUTHORS><AUTHOR>Biro,P.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>Mittal,S.</AUTHOR></AUTHORS><YEAR>2009</YEAR><TITLE>Size versus stability in the Marriage problem</TITLE><PLACE_PUBLISHED>Proceedings of WAOA 2008: the 6th Workshop on
Approximation and Online Algorithms, volume 5426
of Lecture Notes in Computer Science</PLACE_PUBLISHED><PUBLISHER>Springer</PUBLISHER><PAGES>15-28</PAGES><LABEL>Biro:2009:9113</LABEL><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.</ABSTRACT><URL>http://dx.doi.org/10.1007/978-3-540-93980-1_2</URL></RECORD></RECORDS></XML>