Computing at Glasgow University
Paper ID: 7815
DCS Tech Report Number: TR-2004-182

Pareto optimality in the Roommates problem
Abraham,D.J. Manlove,D.F.

Publication Type: Tech Report (internal)
Appeared in: DCS Tech Report
Page Numbers : 1-16
Publisher: N/A
Year: 2004

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 NP-hard, though approximable within 2. We also show that the problem of finding a Pareto optimal matching with the fewest number of blocking pairs is NP-hard. However, for a fixed integer K, we give a polynomial-time algorithm that constructs a Pareto optimal matching with at most K blocking pairs, or reports that no such matching exists.

PS/PS.GZ PDF Bibtex entry Endnote XML