Abstract
We consider the problem of computing popular matchings in a bipartite graph \(G = (\mathcal {R}\,\cup \, \mathcal {H}, E)\) where \(\mathcal {R}\) and \(\mathcal {H}\) denote a set of residents and a set of hospitals respectively. Each hospital h has a positive capacity denoting the number of residents that can be matched to h. The residents and the hospitals specify strict preferences over each other. This is the well-studied Hospital Residents (HR) problem which is a generalization of the Stable Marriage (SM) problem. The goal is to assign residents to hospitals optimally while respecting the capacities of the hospitals. Stability is a well-accepted notion of optimality in such problems. However, motivated by the need for larger cardinality matchings, alternative notions of optimality like popularity have been investigated in the SM setting. In this paper, we consider a generalized HR setting – namely the Laminar Classified Stable Matchings (LCSM\(^+\)) problem. Here, additionally, hospitals can specify classifications over residents in their preference lists and classes have upper quotas. We show the following new results: We define a notion of popularity and give a structural characterization of popular matchings for the LCSM\(^+\) problem. Assume \(n = |\mathcal {R}| + |\mathcal {H}|\) and \(m = |E|\). We give an O(mn) time algorithm for computing a maximum cardinality popular matching in an LCSM\(^+\) instance. We give an \(O(mn^2)\) time algorithm for computing a matching that is popular amongst the maximum cardinality matchings in an LCSM\(^+\) instance.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We use HR\(^+\) instead of HR for consistency with other problems discussed in the paper. The \(^+\) signifies that the hospitals do not specify a lower quota.
References
Abraham, D.J., Irving, R.W., Kavitha, T., Mehlhorn, K.: Popular matchings. SIAM J. Comput. 37(4), 1030–1045 (2007)
Abraham, D.J., Irving, R.W., Manlove, D.F.: Two algorithms for the student-project allocation problem. J. Discrete Algorithms 5(1), 73–90 (2007)
Biró, P., Manlove, D., Mittal, S.: Size versus stability in the marriage problem. Theoret. Comput. Sci. 411(16–18), 1828–1841 (2010)
Brandl, F., Kavitha, T.: Popular Matchings with Multiple Partners. CoRR, abs/1609.07531 (2016)
Cseh, Á., Kavitha, T.: Popular edges and dominant matchings. In: Proceedings of the Eighteenth Conference on Integer Programming and Combinatorial Optimization, pp. 138–151 (2016)
Fleiner, T., Kamiyama, N.: A matroid approach to stable matchings with lower quotas. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 135–142 (2012)
Gale, D., Shapley, L.: College admissions and the stability of marriage. Am. Math. Monthly 69, 9–14 (1962)
Gärdenfors, P.: Match making: assignments based on bilateral preferences. Behav. Sci. 20, 166–173 (1975)
Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Boston (1989)
Huang, C.-C.: Classified stable matching. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1235–1253 (2010)
Huang, C.-C., Kavitha, T.: Popular matchings in the stable marriage problem. In: Proceedings of 38th International Colloquium on Automata, Languages and Programming, pp. 666–677 (2011)
Kamiyama, N.: Popular matchings with two-sided preference lists and matroid constraints. Technical report MI 2016–13 (2016)
Kavitha, T.: A size-popularity tradeoff in the stable marriage problem. SIAM J. Comput. 43(1), 52–71 (2014)
Nasre, M., Rawat, A.: Popularity in the Generalized Hospital Residents Setting. CoRR, abs/1609.07650 (2016)
Acknowledgement
We thank Prajakta Nimbhorkar for helpful discussions. We thank the anonymous reviewers whose comments have improved the presentation.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Nasre, M., Rawat, A. (2017). Popularity in the Generalized Hospital Residents Setting. In: Weil, P. (eds) Computer Science – Theory and Applications. CSR 2017. Lecture Notes in Computer Science(), vol 10304. Springer, Cham. https://doi.org/10.1007/978-3-319-58747-9_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-58747-9_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-58746-2
Online ISBN: 978-3-319-58747-9
eBook Packages: Computer ScienceComputer Science (R0)