Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


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.


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.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Abraham, D.J.; Biro, P.; Manlove, D.F. (2006)
Publisher: Springer Verlag
Languages: English
Types: Other
Subjects: QA75
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 1. K. Cechla´rov´a and T. Fleiner. On a generalization of the stable roommates problem. ACM Transactions on Algorithms, 1(1):143-156, 2005.
    • 2. K. Eriksson and P. Strimling. How unstable are matchings from decentralized mate search? Preprint, 2005. Submitted for publication.
    • 3. D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962.
    • 4. D. Gusfield and R.W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.
    • 5. F. Harary. Maximum versus minimum invariants for graphs. J. Graph Theory, 7:275-284, 1983.
    • 6. J.D. Horton and K. Kilakos. Minimum edge dominating sets. SIAM J. Discrete Mathematics, 6:375-387, 1993.
    • 7. R.W. Irving. An efficient algorithm for the “stable roommates” problem. J. Algorithms, 6:577-595, 1985.
    • 8. R.W. Irving and D.F. Manlove. The Stable Roommates Problem with Ties. J. Algorithms, 43:85-105, 2002.
    • 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.
    • 11. M. Niederle and A.E. Roth. Market culture: How norms governing explording offers affect market performance. NBER working paper 10256, January 2004.
    • 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.
  • No related research data.
  • No similar publications.

Share - Bookmark

Download from

Cite this article