Abstract
We study a generalisation of the stable matching problem to the many-to-many variant in which vertices of the bipartite graph \(G = (A \cup B, E)\) may involve ties in their preference lists. We investigate the notion of strong stability and give an \(O(m\sum _{y \in B}b(y))\) algorithm for computing a strongly stable b-matching optimal for vertices of A, where we denote \(m = |E|\). Our result improves on the previous algorithm by Chen and Ghosh [2]. The main technique allowing us to speed up the algorithm is a generalisation of the notion of level-maximal matchings [8] to the case of b-matchings.
As a byproduct of our results we obtain an O(nm) algorithm for a many-to-one restriction of the problem also known as the hospitals-residents problem, where we denote \(n = |A \cup B|\), \(m = |E|\). The previous best algorithm had an \(O(m\sum _{y \in B} b(y))\) runtime [8].
Partly supported by Polish National Science Center grant 2018/29/B/ST6/02633.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Baïou, M., Balinski, M.: Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry). Discrete Appl. Math. 101(1–3), 1–12 (2000)
Chen, N., Ghosh, A.: Strongly stable assignment. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6347, pp. 147–158. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15781-3_13
Gusfield, D., Irving, R.W.: The Stable Marriage Problem - Structure and Algorithms. Foundations of Computing Series. MIT Press, Cambridge (1989)
Irving, R.W.: An efficient algorithm for the “stable roommates” problem. J. Algorithms 6(4), 577–595 (1985)
Irving, R.W.: Stable marriage and indifference. Discrete Appl. Math. 48(3), 261–272 (1994)
Irving, R.W., Manlove, D.F., Scott, S.: Strong stability in the hospitals/residents problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 439–450. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36494-3_39
Irving, R.W., Scott, S.: The stable fixtures problem - a many-to-many extension of stable roommates. Discrete Appl. Math. 155(16), 2118–2129 (2007)
Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.E.: Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem. ACM Trans. Algorithms 3(2), 15 (2007)
Kunysz, A.: The strongly stable roommates problem. In: Sankowski, P., Zaroliagis, C.D. (eds.) 24th Annual European Symposium on Algorithms, ESA 2016, Aarhus, Denmark, 22–24 August 2016, Volume 57 of LIPIcs, pp. 60:1–60:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)
Kunysz, A., Paluch, K.E., Ghosal, P.: Characterisation of strongly stable matchings. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10–12 January 2016, pp. 107–119 (2016)
Malhotra, V.S.: On the stability of multiple partner stable marriages with ties. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 508–519. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30140-0_46
Manlove, D.F.: Stable marriage with ties and unacceptable partners. Technical report, University of Glasgow (1999)
Manlove, D.F.: The structure of stable marriage with indifference. Discrete Appl. Math. 122(1–3), 167–181 (2002)
Manlove, D.F.: Algorithmics of Matching Under Preferences, Volume 2 of Series on Theoretical Computer Science. World Scientific (2013)
Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92(6), 991–2016 (1984)
Scott, S.: A study of stable marriage problems with ties. Ph.D. thesis, University of Glasgow (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Kunysz, A. (2019). A Faster Algorithm for the Strongly Stable b-Matching Problem. In: Heggernes, P. (eds) Algorithms and Complexity. CIAC 2019. Lecture Notes in Computer Science(), vol 11485. Springer, Cham. https://doi.org/10.1007/978-3-030-17402-6_25
Download citation
DOI: https://doi.org/10.1007/978-3-030-17402-6_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-17401-9
Online ISBN: 978-3-030-17402-6
eBook Packages: Computer ScienceComputer Science (R0)