<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>8904</REFNUM><AUTHORS><AUTHOR>Biro,P.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>Mittal,S.</AUTHOR></AUTHORS><YEAR>2008</YEAR><TITLE>Size Versus Stability in the Marriage Problem</TITLE><PLACE_PUBLISHED>DCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><ISBN>TR-2008-283</ISBN><LABEL>Biro:2008:8904</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></RECORD></RECORDS></XML>