The stable roommates problem with ties

Article English OPEN
Irving, R. W. ; Manlove, D.F. (2002)

We study the variant of the well-known stable roommates problem in which participants are permitted to express ties in their preference lists. In this setting, more than one definition of stability is possible. Here we consider two of these stability criteria, so-called super-stability and weak stability. We present a linear–time algorithm for finding a super-stable matching if one exists, given a stable roommates instance with ties. This contrasts with the known NP-hardness of the analogous problem under weak stability. We also extend our algorithm to cope with preference lists that are incomplete and/or partially ordered. On the other hand, for a given stable roommates instance with ties and incomplete lists, we show that the weakly stable matchings may be of different sizes and the problem of finding a maximum cardinality weakly stable matching is NP-hard, though approximable within a factor of 2.
  • References (16)
    16 references, page 1 of 2

    [1] T. Feder, N. Megiddo, and S. Plotkin. A sublinear parallel algorithm for stable matching. In Proceedings of SODA '94: the 5th ACM-SIAM Symposium on Discrete Algorithms, pages 632{637. ACM-SIAM, 1994.

    [2] D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9{15, 1962.

    [3] M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, San Francisco, CA., 1979.

    [4] D. Gus¯eld. The structure of the stable roommate problem { e±cient representation and enumeration of all stable assignments. SIAM Journal on Computing, 17(4):742{ 769, 1988.

    [5] D. Gus¯eld and R.W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.

    [6] J.D. Horton and K. Kilakos. Minimum edge dominating sets. SIAM Journal on Discrete Mathematics, 6:375{387, 1993.

    [7] R.W. Irving. An e±cient algorithm for the \stable roommates" problem. Journal of Algorithms, 6:577{595, 1985.

    [8] R.W. Irving. On the stable room-mates problem. Technical Report CSC/86/R5, University of Glasgow, Department of Computing Science, 1986.

    [9] R.W. Irving. Stable marriage and indi®erence. Discrete Applied Mathematics, 48:261{ 272, 1994.

    [10] R.W. Irving, D.F. Manlove, and S. Scott. The Hospitals/Residents problem with Ties. In Proceedings of SWAT 2000: the 7th Scandinavian Workshop on Algorithm Theory, volume 1851 of Lecture Notes in Computer Science, pages 259{271. Springer-Verlag, 2000.

  • Similar Research Results (1)
  • Metrics
    No metrics available
Share - Bookmark