Document Open Access Logo

An Algorithm for the Maximum Weight Strongly Stable Matching Problem

Author Adam Kunysz

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.42.pdf
  • Filesize: 441 kB
  • 13 pages

Document Identifiers

Author Details

Adam Kunysz
  • Institute of Computer Science, University of Wrocław, Poland

Funding

Partly supported by Polish National Science Center grant UMO-2013/11/B/ST6/01748.

Cite As Get BibTex

Adam Kunysz. An Algorithm for the Maximum Weight Strongly Stable Matching Problem. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.42

Abstract

An instance of the maximum weight strongly stable matching problem with incomplete lists and ties is an undirected bipartite graph G = (A cup B, E), with an adjacency list being a linearly ordered list of ties, which are vertices equally good for a given vertex. We are also given a weight function w on the set E. An edge (x, y) in E setminus M is a blocking edge for M if by getting matched to each other neither of the vertices x and y would become worse off and at least one of them would become better off. A matching is strongly stable if there is no blocking edge with respect to it. The goal is to compute a strongly stable matching of maximum weight with respect to w.
We give a polyhedral characterisation of the problem and prove that the strongly stable matching polytope is integral. This result implies that the maximum weight strongly stable matching problem can be solved in polynomial time. Thereby answering an open question by Gusfield and Irving [Dan Gusfield and Robert W. Irving, 1989]. The main result of this paper is an efficient O(nm log{(Wn)}) time algorithm for computing a maximum weight strongly stable matching, where we denote n = |V|, m = |E| and W is a maximum weight of an edge in G. For small edge weights we show that the problem can be solved in O(nm) time. Note that the fastest known algorithm for the unweighted version of the problem has O(nm) runtime [Telikepalli Kavitha et al., 2007]. Our algorithm is based on the rotation structure which was constructed for strongly stable matchings in [Adam Kunysz et al., 2016].

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Stable marriage
  • Strongly stable matching
  • Weighted matching
  • Rotation

Metrics

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

References

  1. Tomás Feder. A New Fixed Point Approach for Stable Networks and Stable Marriages. J. Comput. Syst. Sci., 45(2):233-284, 1992. URL: http://dx.doi.org/10.1016/0022-0000(92)90048-N.
  2. Tomás Feder. Network Flow and 2-Satisfiability. Algorithmica, 11(3):291-319, 1994. URL: http://dx.doi.org/10.1007/BF01240738.
  3. 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.
  4. Harold N. Gabow and Robert Endre Tarjan. Faster Scaling Algorithms for Network Problems. SIAM J. Comput., 18(5):1013-1036, 1989. URL: http://dx.doi.org/10.1137/0218069.
  5. David Gale and Lloyd S Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1):9-15, 1962. URL: http://dx.doi.org/10.2307/2312726.
  6. Dan Gusfield and Robert W. Irving. The Stable marriage problem - structure and algorithms. Foundations of computing series. MIT Press, 1989. Google Scholar
  7. 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.
  8. Kazuo Iwama, David Manlove, Shuichi Miyazaki, and Yasufumi Morita. Stable Marriage with Incomplete Lists and Ties. ICALP'99, Prague, Czech Republic, July 11-15, 1999, pages 443-452, 1999. URL: http://dx.doi.org/10.1007/3-540-48523-6_41.
  9. 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.
  10. Zoltán Király. Better and Simpler Approximation Algorithms for the Stable Marriage Problem. Algorithmica, 60(1):3-20, 2011. URL: http://dx.doi.org/10.1007/s00453-009-9371-7.
  11. Adam Kunysz. The Strongly Stable Roommates Problem. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 60:1-60:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.60.
  12. 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.
  13. David Manlove, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, and Yasufumi Morita. Hard variants of stable marriage. Theor. Comput. Sci., 276(1-2):261-279, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00206-7.
  14. David F. Manlove. Stable marriage with ties and unacceptable partners. Technical report, University of Glasgow, 1999. Google Scholar
  15. 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.
  16. 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.
  17. Eric McDermid. A 3/2-Approximation Algorithm for General Stable Marriage. ICALP 2009, Rhodes, Greece, July 5-12, 2009, pages 689-700, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02927-1_57.
  18. Katarzyna E. Paluch. Faster and Simpler Approximation of Stable Matchings. Algorithms, 7(2):189-202, 2014. URL: http://dx.doi.org/10.3390/a7020189.
  19. A. E. Roth. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, 92(6):991-2016, 1984. Google Scholar
  20. Alvin E. Roth, Uriel G. Rothblum, and John H. Vande Vate. Stable Matchings, Optimal Assignments, and Linear Programming. Math. Oper. Res., 18(4):803-828, 1993. URL: http://dx.doi.org/10.1287/moor.18.4.803.
  21. Uriel G. Rothblum. Characterization of stable matchings as extreme points of a polytope. Math. Program., 54:57-67, 1992. URL: http://dx.doi.org/10.1007/BF01586041.
  22. A. Schrijver. Combinatorial Optimization - Polyhedra and Efficiency. Springer, 2003. Google Scholar
  23. Daniel Dominic Sleator and Robert Endre Tarjan. A Data Structure for Dynamic Trees. J. Comput. Syst. Sci., 26(3):362-391, 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90006-5.
  24. Chung-Piaw Teo and Jay Sethuraman. The Geometry of Fractional Stable Matchings and Its Applications. Math. Oper. Res., 23(4):874-891, 1998. URL: http://dx.doi.org/10.1287/moor.23.4.874.
  25. J.H. Vande Vate. Linear programming brings marital bliss. Operations Research Letters, 8:147–153, 1989. URL: http://dx.doi.org/10.1016/0167-6377(89)90041-2.
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