Paper ID: 9380
DCS Tech Report Number: TR2011328
"Almost stable" matchings in the Roommates problem with bounded preference lists
Biro,P.
Manlove,D.F.
McDermid,E.J.
Publication Type:
Tech Report (internal)
Appeared in:
DCS Technical Report Series
Page Numbers : 117
Publisher: Dept of Computing Science, University of Glasgow
Year: 2011
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 NPhard and
not approximable within n^{½ε}, for
any ε>0, unless P=NP, where n 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 d. We show
that, even if d=3, there is some c>1 such that
the problem of finding a matching with the minimum number of
blocking pairs is not approximable within c unless
P=NP. On the other hand we show that the problem is
solvable in polynomial time for d≤2, and we
give a (2d3)approximation algorithm for fixed
d≥3. If the given lists satisfy an additional
condition (namely the absence of a socalled elitist odd
party  a structure that is unlikely to exist in
general), the performance guarantee improves to 2d4.
Keywords: Stable Roommates problem; blocking pair; APXhardness; polynomialtime algorithm; approximation algorithm
