<XML><RECORDS><RECORD><REFERENCE_TYPE>3</REFERENCE_TYPE><REFNUM>7953</REFNUM><AUTHORS><AUTHOR>Abraham,D.J.</AUTHOR><AUTHOR>Biro,P.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>2006</YEAR><TITLE>"Almost Stable" Matchings in the Roommates Problem</TITLE><PLACE_PUBLISHED>In Proceedings of WAOA 2005: the 3rd Workshop on Approximation and Online Algorithms, volume 3879 of Lecture Notes in Computer Science</PLACE_PUBLISHED><PUBLISHER>Springer Verlag</PUBLISHER><PAGES>1-14</PAGES><LABEL>Abraham:2006:7953</LABEL><ABSTRACT>An instance of the classical Stable Roommates problem (SR) need not admit a stable matching. This motivates the problem of finding a matching that is "as stable as possible'', i.e. admits the fewest number of blocking pairs. In this paper we prove that, given an SR instance with <i>n</i> agents, in which all preference lists are complete, the problem of finding a matching with the fewest number of blocking pairs is NP-hard and not approximable within <i style='mso-bidi-font-style:normal'>n</i><sup>1/2-</sup><i style='mso-bidi-font-style:normal'><sup><span style='font-family:Symbol; mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"; mso-char-type:symbol;mso-symbol-font-family:Symbol'><span style='mso-char-type: symbol;mso-symbol-font-family:Symbol'>e</span></span></sup></i>, for any <i style='mso-bidi-font-style:normal'><span lang=IT style='font-family:Symbol;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family: "Times New Roman";mso-ansi-language:IT;mso-char-type:symbol;mso-symbol-font-family: Symbol'><span style='mso-char-type:symbol;mso-symbol-font-family:Symbol'>e</span></span></i><span lang=IT style='mso-ansi-language:IT'>>0</span>, unless P=NP. If the preference lists contain ties, we improve this result to <i style='mso-bidi-font-style:normal'>n</i><sup>1-</sup><i style='mso-bidi-font-style:normal'><sup><span style='font-family:Symbol; mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"; mso-char-type:symbol;mso-symbol-font-family:Symbol'><span style='mso-char-type: symbol;mso-symbol-font-family:Symbol'>e</span></span></sup></i>. Also, we show that, given an integer <i>K</i> and an SR instance <i>I</i> in which all preference lists are complete, the problem of deciding whether <i>I</i> admits a matching with exactly <i>K</i> blocking pairs is NP-complete. By contrast, if <i>K</i> is constant, we give a polynomial-time algorithm that finds a matching with at most (or exactly) <i>K</i> blocking pairs, or reports that no such matching exists. Finally, we give upper and lower bounds for the minimum number of blocking pairs over all matchings in terms of some properties of a stable partition, given an SR instance <i>I</i>.</ABSTRACT><URL>http://dx.doi.org/10.1007/11671411_1</URL></RECORD></RECORDS></XML>