Document Open Access Logo

Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower Quotas

Authors Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, Ankita Sarkar

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.30.pdf
  • Filesize: 0.77 MB
  • 21 pages

Document Identifiers

Author Details

Meghana Nasre
  • IIT Madras, Chennai, India
Prajakta Nimbhorkar
  • Chennai Mathematical Institute, India
  • UMI ReLaX, Chennai, India
Keshav Ranjan
  • IIT Madras, Chennai, India
Ankita Sarkar
  • Dartmouth College, Hanover, NH, USA

Funding

  • Nasre, Meghana: Partially funded by SERB grant CRG/2019/004757.
  • Nimbhorkar, Prajakta: Partially funded by Infosys Grant and SERB grant CRG/2019/004757.
  • Sarkar, Ankita: Part of the work was done when the author was a Master’s student at Chennai Mathematical Institute, India.

Cite As Get BibTex

Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, and Ankita Sarkar. Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower Quotas. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.FSTTCS.2021.30

Abstract

We consider the hospital-residents problem where both hospitals and residents can have lower quotas. The input is a bipartite graph G = (ℛ∪ℋ,E), each vertex in ℛ∪ℋ has a strict preference ordering over its neighbors. The sets ℛ and ℋ denote the sets of residents and hospitals respectively. Each hospital has an upper and a lower quota denoting the maximum and minimum number of residents that can be assigned to it. Residents have upper quota equal to one, however, there may be a requirement that some residents must not be left unassigned in the output matching. We call this as the residents' lower quota. 
We show that whenever the set of matchings satisfying all the lower and upper quotas is non-empty, there always exists a matching that is popular among the matchings in this set. We give a polynomial-time algorithm to compute such a matching.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • Matching
  • Popularity
  • Lower quota
  • Preferences

Metrics

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

References

  1. David J Abraham, Robert W Irving, Telikepalli Kavitha, and Kurt Mehlhorn. Popular matchings. SIAM Journal on Computing, 37(4):1030-1045, 2007. Google Scholar
  2. Péter Biró, Robert W Irving, and David F Manlove. Popular matchings in the marriage and roommates problems. In International Conference on Algorithms and Complexity, pages 97-108. Springer, 2010. Google Scholar
  3. Florian Brandl and Telikepalli Kavitha. Two problems in max-size popular matchings. Algorithmica, 81(7):2738-2764, 2019. Google Scholar
  4. Ágnes Cseh and Telikepalli Kavitha. Popular edges and dominant matchings. Mathematical Programming, 172(1):209-229, 2018. Google Scholar
  5. Yuri Faenza and Telikepalli Kavitha. Quasi-popular matchings, optimality, and extended formulations. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 325-344. SIAM, 2020. Google Scholar
  6. Tamás Fleiner and Naoyuki Kamiyama. A matroid approach to stable matchings with lower quotas. Math. Oper. Res., 41(2):734-744, 2016. URL: https://doi.org/10.1287/moor.2015.0751.
  7. Peter Gärdenfors. Match making: assignments based on bilateral preferences. Behavioral Science, 20(3):166-173, 1975. Google Scholar
  8. Mizuki Hirakawa, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita. On the structure of popular matchings in the stable marriage problem-who can join a popular matching. In the 3rd International Workshop on Matching under Preferences (MATCH-UP), 2015. Google Scholar
  9. Chien-Chung Huang. Classified stable matching. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pages 1235-1253, 2010. URL: https://doi.org/10.1137/1.9781611973075.99.
  10. Chien-Chung Huang and Telikepalli Kavitha. Popular matchings in the stable marriage problem. Information and Computation, 222:180-194, 2013. Google Scholar
  11. Chien-Chung Huang and Telikepalli Kavitha. Popularity, mixed matchings, and self-duality. Mathematics of Operations Research, 2021. Google Scholar
  12. Telikepalli Kavitha. A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing, 43(1):52-71, 2014. Google Scholar
  13. Telikepalli Kavitha. Popular half-integral matchings. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  14. Telikepalli Kavitha. Popular matchings with one-sided bias. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  15. Telikepalli Kavitha. Matchings, critical nodes, and popular solutions. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021 (To Appear), 2021. Google Scholar
  16. Telikepalli Kavitha. Maximum Matchings and Popularity. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198, pages 85:1-85:21, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.85.
  17. Zoltán Király. Better and simpler approximation algorithms for the stable marriage problem. Algorithmica, 60(1):3-20, 2011. Google Scholar
  18. A. M. Krishnapriya, Meghana Nasre, Prajakta Nimbhorkar, and Amit Rawat. How good are popular matchings? In 17th International Symposium on Experimental Algorithms, SEA 2018, pages 9:1-9:14, 2018. URL: https://doi.org/10.4230/LIPIcs.SEA.2018.9.
  19. Matthias Mnich and Ildikó Schlotter. Stable matchings with covering constraints: A complete computational trichotomy. Algorithmica, 82(5):1136-1188, 2020. Google Scholar
  20. Meghana Nasre and Prajakta Nimbhorkar. Popular matchings with lower quotas. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, pages 44:1-44:15, 2017. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2017.44.
  21. Meghana Nasre and Amit Rawat. Popularity in the generalized hospital residents setting. In International Computer Science Symposium in Russia, pages 245-259. Springer, 2017. 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