Paper ID: 7815
DCS Tech Report Number: TR2004182
Pareto optimality in the Roommates problem
Abraham,D.J.
Manlove,D.F.
Publication Type:
Tech Report (internal)
Appeared in:
DCS Tech Report
Page Numbers : 116
Publisher: N/A
Year: 2004
Abstract:
We consider Pareto optimal matchings as a means of coping
with instances of
the Stable Roommates problem (SR) that do not admit a stable
matching.
Given an instance I of SR, we show that the problem of
finding a maximum
Pareto optimal matching is solvable in
O(\sqrt{n\alpha(m,n)}m\log^{3/2} n)
time, where n is the number of agents and m is the total
length of the
preference lists in I. By contrast we prove that the
problem of finding a
minimum Pareto optimal matching is NPhard, though
approximable within 2.
We also show that the problem of finding a Pareto optimal
matching with the
fewest number of blocking pairs is NPhard. However, for a
fixed integer
K, we give a polynomialtime algorithm that constructs a
Pareto
optimal matching with at most K blocking pairs, or reports
that no such
matching exists.
