<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>