Document Open Access Logo

The Strongly Stable Roommates Problem

Author Adam Kunysz

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.60.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Adam Kunysz

Cite As Get BibTex

Adam Kunysz. The Strongly Stable Roommates Problem. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.60

Abstract

An instance of the strongly stable roommates problem with incomplete lists and ties (SRTI) is an undirected non-bipartite graph G = (V,E), with an adjacency list being a linearly ordered list of ties, which are vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching M is a set of vertex-disjoint edges. An edge {x, y} in E\M is a blocking edge for M if x is either unmatched or strictly prefers y to its current partner in M, and y is either unmatched or strictly prefers x to its current partner in M or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We present an O(nm) time algorithm for computing a strongly stable matching, where we denote n = |V| and m = |E|. The best previously known solution had running time O(m^2) [Scott, 2005]. We also give a characterisation of the set of all strongly stable matchings. We show that there exists a partial order with O(m) elements representing the set of all strongly stable matchings, and we give an O(nm) algorithm for constructing such a representation. Our algorithms are based on a simple reduction to the bipartite version of the problem.

Subject Classification

Keywords
  • strongly stable matching
  • stable roommates
  • rotations
  • matching theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Brian C. Dean and Siddharth Munshi. Faster algorithms for stable allocation problems. Algorithmica, 58(1):59-81, 2010. URL: http://dx.doi.org/10.1007/s00453-010-9416-y.
  2. Tamás Fleiner, Robert W. Irving, and David F. Manlove. Efficient algorithms for generalized stable marriage and roommates problems. Theor. Comput. Sci., 381(1-3):162-176, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.04.029.
  3. Dan Gusfield and Robert W. Irving. The Stable marriage problem - structure and algorithms. Foundations of computing series. MIT Press, 1989. Google Scholar
  4. Robert W. Irving. An efficient algorithm for the "stable roommates" problem. J. Algorithms, 6(4):577-595, 1985. URL: http://dx.doi.org/10.1016/0196-6774(85)90033-1.
  5. Robert W. Irving. Stable marriage and indifference. Discrete Applied Mathematics, 48(3):261-272, 1994. URL: http://dx.doi.org/10.1016/0166-218X(92)00179-P.
  6. Robert W. Irving and David F. Manlove. The stable roommates problem with ties. J. Algorithms, 43(1):85-105, 2002. URL: http://dx.doi.org/10.1006/jagm.2002.1219.
  7. Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna E. Paluch. Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem. ACM Trans. Algorithms, 3(2), 2007. URL: http://dx.doi.org/10.1145/1240233.1240238.
  8. Adam Kunysz, Katarzyna E. Paluch, and Pratik Ghosal. Characterisation of strongly stable matchings. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 107-119, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch8.
  9. David F. Manlove. Stable marriage with ties and unacceptable partners. Technical report, University of Glasgow, 1999. Google Scholar
  10. David F. Manlove. The structure of stable marriage with indifference. Discrete Applied Mathematics, 122(1-3):167-181, 2002. URL: http://dx.doi.org/10.1016/S0166-218X(01)00322-5.
  11. David F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science. WorldScientific, 2013. URL: http://dx.doi.org/10.1142/8591.
  12. Silvio Micali and Vijay V. Vazirani. An o(sqrt(|v|) |e|) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 17-27. IEEE Computer Society, 1980. URL: http://dx.doi.org/10.1109/SFCS.1980.12.
  13. Nitsan Perach, Julia Polak, and Uriel G. Rothblum. A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the technion. Int. J. Game Theory, 36(3-4):519-535, 2008. URL: http://dx.doi.org/10.1007/s00182-007-0083-4.
  14. Nitsan Perach and Uriel G. Rothblum. Incentive compatibility for the stable matching model with an entrance criterion. Int. J. Game Theory, 39(4):657-667, 2010. URL: http://dx.doi.org/10.1007/s00182-009-0210-5.
  15. Eytan Ronn. Np-complete stable matching problems. J. Algorithms, 11(2):285-304, 1990. URL: http://dx.doi.org/10.1016/0196-6774(90)90007-2.
  16. Sandy Scott. A study of stable marriage problems with ties. PhD thesis, University of Glasgow, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact