<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>½-ε</sup>, for
any ε>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>≤2, and we
give a (2<i>d</i>-3)-approximation algorithm for fixed
<i>d</i>≥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>