You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
An instance of the classical Stable Roommates problem (SR) need not admit a stable matching. This motivates the problem of finding a matching that is “as stable as possible”, i.e. admits the fewest number of blocking pairs. In this paper we prove that, given an SR instance with n agents, in which all preference lists are complete, the problem of finding a matching with the fewest number of blocking pairs is NP-hard and not approximable within n^{\frac{1}{2}-\varepsilon}, for any \varepsilon>0, unless P=NP. If the preference lists contain ties, we improve this result to n^{1-\varepsilon}. Also, we show that, given an integer K and an SR instance I in which all preference lists are complete, the problem of deciding whether I admits a matching with exactly K blocking pairs is NP-complete. By contrast, if K is constant, we give a polynomial-time algorithm that finds a matching with at most (or exactly) K blocking pairs, or reports that no such matching exists. Finally, we give upper and lower bounds for the minimum number of blocking pairs over all matchings in terms of some properties of a stable partition, given an SR instance I.
9. D.E. Knuth. Mariages Stables, Les Presses de L'Universit´e de Montr´eal, 1976.
10. E. Kujansuu, T. Lindberg, and E. M¨akinen. The stable roommates problem and chess tournament pairings. Divulgaciones Matem´aticas, 7(1):19-28, 1999.
12. B.G. Pittel and R.W. Irving. An upper bound for the solvability probability of a random stable roommates instance. Rand. Struct. Algorithms, 5(3):465-486, 1994.
13. E. Ronn. NP-complete stable matching problems. J. Algorithms, 11:285-304, 1990.
14. A.E. Roth, T. S¨onmez, and M. Utku U¨nver. Pairwise kidney exchange. To appear in Journal of Economic Theory.
15. A.E. Roth and M.A.O. Sotomayor. Two-sided matching: a study in game-theoretic modeling and analysis Cambridge University Press, 1990.
16. J.J.M. Tan. A necessary and sufficient condition for the existence of a complete stable matching. J. Algorithms, 12:154-178, 1991.
17. J.J.M. Tan. Stable matchings and stable partitions. International J. Computer Mathematics, 39:11-20, 1991.