<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>9380</REFNUM><AUTHORS><AUTHOR>Biro,P.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR><AUTHOR>McDermid,E.J.</AUTHOR></AUTHORS><YEAR>2011</YEAR><TITLE>"Almost stable" matchings in the Roommates problem with bounded preference lists</TITLE><PLACE_PUBLISHED>DCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><PAGES>1-17</PAGES><ISBN>TR-2011-328</ISBN><LABEL>Biro:2011:9380</LABEL><KEYWORDS><KEYWORD>Stable Roommates problem; blocking pair; APX-hardness; polynomial-time algorithm; approximation algorithm</KEYWORD></KEYWORDS<ABSTRACT>An instance of the classical Stable Roommates problem (SR) need not admit a stable matching. Previous work has considered the problem of finding a matching that is "as stable as possible", i.e., admits the fewest number of blocking pairs. It is known that this problem is NP-hard and not approximable within <i>n</i><sup>&#189-&#949</sup>, for any &#949>0, unless P=NP, where <i>n</i> is the number of agents in a given SR instance. In this paper we extend the study to the Stable Roommates problem with Incomplete lists. In particular, we consider the case that the lengths of the lists are bounded by some integer <i>d</i>. We show that, even if <i>d</i>=3, there is some <i>c</i>>1 such that the problem of finding a matching with the minimum number of blocking pairs is not approximable within <i>c</i> unless P=NP. On the other hand we show that the problem is solvable in polynomial time for <i>d</i>&#8804;2, and we give a (2<i>d</i>-3)-approximation algorithm for fixed <i>d</i>&#8805;3. If the given lists satisfy an additional condition (namely the absence of a so-called <i>elitist odd party</i> -- a structure that is unlikely to exist in general), the performance guarantee improves to 2<i>d</i>-4.</ABSTRACT></RECORD></RECORDS></XML>