Nothing Special   »   [go: up one dir, main page]

Skip to main content

Popularity in the Generalized Hospital Residents Setting

  • Conference paper
  • First Online:
Computer Science – Theory and Applications (CSR 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10304))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 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

  1. Abraham, D.J., Irving, R.W., Kavitha, T., Mehlhorn, K.: Popular matchings. SIAM J. Comput. 37(4), 1030–1045 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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)

    Article  MathSciNet  MATH  Google Scholar 

  3. Biró, P., Manlove, D., Mittal, S.: Size versus stability in the marriage problem. Theoret. Comput. Sci. 411(16–18), 1828–1841 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  4. Brandl, F., Kavitha, T.: Popular Matchings with Multiple Partners. CoRR, abs/1609.07531 (2016)

    Google Scholar 

  5. Cseh, Á., Kavitha, T.: Popular edges and dominant matchings. In: Proceedings of the Eighteenth Conference on Integer Programming and Combinatorial Optimization, pp. 138–151 (2016)

    Google Scholar 

  6. 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)

    Google Scholar 

  7. Gale, D., Shapley, L.: College admissions and the stability of marriage. Am. Math. Monthly 69, 9–14 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  8. Gärdenfors, P.: Match making: assignments based on bilateral preferences. Behav. Sci. 20, 166–173 (1975)

    Article  Google Scholar 

  9. Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Boston (1989)

    MATH  Google Scholar 

  10. Huang, C.-C.: Classified stable matching. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1235–1253 (2010)

    Google Scholar 

  11. 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)

    Google Scholar 

  12. Kamiyama, N.: Popular matchings with two-sided preference lists and matroid constraints. Technical report MI 2016–13 (2016)

    Google Scholar 

  13. Kavitha, T.: A size-popularity tradeoff in the stable marriage problem. SIAM J. Comput. 43(1), 52–71 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  14. Nasre, M., Rawat, A.: Popularity in the Generalized Hospital Residents Setting. CoRR, abs/1609.07650 (2016)

    Google Scholar 

Download references

Acknowledgement

We thank Prajakta Nimbhorkar for helpful discussions. We thank the anonymous reviewers whose comments have improved the presentation.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Amit Rawat .

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics