Min-Cost Popular Matchings in a Hospitals/Residents Instance with Complete Preferences

References

• [1] Abdulkadiroğlu A, Sönmez T (2003) School choice: A mechanism design approach. Amer. Econom. Rev. 93(3):729–747.Crossref, Google Scholar
• [2] Askalidis G, Immorlica N, Kwanashie A, Manlove D, Pountourakis E (2013) Socially stable matchings in the hospitals/residents problem. Dehne F, Solis-Oba R, Sack JR, eds. Proc. 13th Internat. Sympos. Algorithms Data Structures, WADS 2013 (Springer, Berlin), 85–96.Google Scholar
• [3] Baswana S, Chakrabarti PP, Chandran S, Kanoria Y, Patange U (2019) Centralized admissions for engineering colleges in India. INFORMS J. Appl. Anal. 49(5):338–354.Link, Google Scholar
• [4] Biro P, Irving RW, Manlove DF (2010) Popular matchings in the marriage and roommates problems. Calamoneri T, Diaz J, eds. Proc. Seventh Internat. Conf. Algorithms Complexity, CIAC 2010 (Springer, Berlin), 97–108.Google Scholar
• [5] Blair C (1988) The lattice structure of the set of stable matchings with multiple partners. Math. Oper. Res. 13(4):619–628.Link, Google Scholar
• [6] Brandl F, Kavitha T (2019) Two problems in max-size popular matchings. Algorithmica 81(7):2738–2764.Crossref, Google Scholar
• [7] Canadian Resident Matching Service (1970) The match. Accessed August 31, 2025, https://www.carms.ca/the-match.Google Scholar
• [8] Cseh A (2017) Popular matchings, Chapter 6. Endriss U, ed. Trends in Computational Social Choice (Lulu.com, Morrisville, NC), 105–122.Google Scholar
• [9] Cseh A, Kavitha T (2018) Popular edges and dominant matchings. Math. Programming 172(1):209–229.Crossref, Google Scholar
• [10] Cseh A, Huang CC, Kavitha T (2017) Popular matchings with two-sided preferences and one-sided ties. SIAM J. Discrete Math. 31(4):2348–2377.Crossref, Google Scholar
• [11] de Condorcet N (1785) Essai Sur L’application de L’analyse à la Probabilité Des Décisions Rendues à la Pluralité Des Voix (L’Imprimerie Royale, Paris).Google Scholar
• [12] Duan R, Wu H, Zhou R (2023) Faster matrix multiplication via asymmetric hashing. Sahai A, ed. Proc. 2023 IEEE 64th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 2129–2138.Google Scholar
• [13] Faenza Y, Kavitha T, Powers V, Zhang X (2019) Popular matchings and limits to tractability. Chan TM, ed. Proc. 30th ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2790–2809.Google Scholar
• [14] Fleiner T (2003) A fixed-point approach to stable matchings and some applications. Math. Oper. Res. 28(1):103–126.Link, Google Scholar
• [15] Gale D, Shapley L (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.Crossref, Google Scholar
• [16] Gale D, Sotomayor M (1985) Some remarks on the stable matching problem. Discrete Appl. Math. 11(3):223–232.Crossref, Google Scholar
• [17] Gärdenfors P (1975) Match making: Assignments based on bilateral preferences. Behavioural Sci. 20(3):166–173.Crossref, Google Scholar
• [18] Gurjar R (2025) TA allocation at computer science and engineering department, IIT Bombay, data provided via personal communication by email, August 8.Google Scholar
• [19] Hamada K, Iwama K, Miyazaki S (2016) The hospitals/residents problem with lower quotas. Algorithmica 74(1):440–465.Crossref, Google Scholar
• [20] Hatfield JW, Milgrom P (2005) Matching with contracts. Amer. Econom. Rev. 95(4):913–935.Crossref, Google Scholar
• [21] Huang CC (2010) Classified stable matching. Charikar M, ed. Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1235–1253.Google Scholar
• [22] Huang CC, Kavitha T (2013) Popular matchings in the stable marriage problem. Inform. Comput. 222:180–194.Crossref, Google Scholar
• [23] Irving RW, Manlove DF, Scott S (2000) The hospitals/residents problem with ties. Halldorsson MM, ed. Proc. Seventh Scandinavian Workshop Algorithm Theory, Lecture Notes in Computer Science 1851 (Springer, Berlin), 259–271.Google Scholar
• [24] Irving RW, Manlove DF, Scott S (2003) Strong stability in the hospitals/residents problem. Alt H, Habib M, eds. Proc. 20th Annual Sympos. Theoret. Aspects Comput. Sci., Lecture Notes in Computer Scienc 2607 (Springer, Berlin), 439–450.Google Scholar
• [25] Jain P, Vaish R (2024) Maximizing Nash social welfare under two-sided preferences. Woodridge M, ed. Proc. AAAI Conf. Artificial Intelligence, vol. 38 (AAAI Press, Palo Alto, CA), 9798–9806.Crossref, Google Scholar
• [26] Jiang S, Song Z, Weinstein O, Zhang H (2021) A faster algorithm for solving general LPs. Williams VV, ed. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 823–832.Google Scholar
• [27] Kavitha T (2014) A size-popularity tradeoff in the stable marriage problem. SIAM J. Comput. 43(1):52–71.Crossref, Google Scholar
• [28] Kavitha T (2021) Matchings, critical nodes, and popular solutions. Bojańczyk M, Chekuri C, eds. Proc. 41st IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci., vol. 25 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 1–25.Google Scholar
• [29] Kavitha T (2024) Maximum matchings and popularity. SIAM J. Discrete Math. 38(2):1202–1221. Google Scholar
• [30] Kavitha T (2025) Matchings, relaxed popularity, and optimality. SIAM J. Discrete Math. 39(2):881–911.Crossref, Google Scholar
• [31] Kavitha T, Makino K (2023) Perfect matchings and popularity in the many-to-many setting. Bouyer P, Srinivasan S, eds. Proc. 43rd IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci. (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 1–16.Google Scholar
• [32] Király T, Mészáros-Karkus Z (2020) Finding strongly popular b-matchings in bipartite graphs. Eur. J. Combin. 88:103105.Crossref, Google Scholar
• [33] Merrill S, Grofman B (1999) A Unified Theory of Voting: Directional and Proximity Spatial Models (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [34] Nasre M (2025) TA allocation at computer science and engineering department, IIT Madras, data provided via personal communication by email on August 12, 2025.Google Scholar
• [35] Nasre M, Nimbhorkar P (2017) Popular matchings with lower quotas. Lokam S, Ramanujam R, eds. Proc. 37th IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci. (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 1–15.Google Scholar
• [36] Nasre M, Rawat A (2017) Popularity in the generalized hospital residents setting. Weil P, ed. Proc. 12th Internat. Comput. Sci. Sympos. Russia CSR 2017, Lecture Notes in Computer Scienc 10304 (Springer, Berlin), 245–259.Google Scholar
• [37] Nasre M, Nimbhorkar P, Ranjan K, Sarkar A (2021) Popular matchings in the hospital-residents problem with two-sided lower quotas. Bojańczyk M, Chekuri C, eds. Proc. 41st IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci. (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 1–21.Google Scholar
• [38] Nasre M, Nimbhorkar P, Ranjan K, Sarkar A (2024) Popular critical matchings in the many-to-many setting. Theoret. Comput. Sci. 982:114281.Crossref, Google Scholar
• [39] National Resident Matching Program (1952) Intro to the match. Accessed August 31, 2025, https://www.nrmp.org/intro-to-the-match/.Google Scholar
• [40] Roth AE (1984) Stability and polarization of interest in job matching. Econometrica 52(1):47–58.Crossref, Google Scholar
• [41] Rothblum UG (1992) Characterization of stable matchings as extreme points of a polytope. Math. Programming 54:57–67.Crossref, Google Scholar
• [42] Sotomayor M (1999) Three remarks on the many-to-many stable matching problem. Math. Soc. Sci. 38(1):55–70.Crossref, Google Scholar
• [43] Subject Board of Biology (2023) Programme outcomes. Accessed August 31, 2025, https://www.tifr.res.in/NAAC/PhD-IPhD%20COURSE%20Outcomes%20Biology%202023-24.pdf.Google Scholar
• [44] Teo CP, Sethuraman J (1998) The geometry of fractional stable matchings and its applications. Math. Oper. Res. 23(4):874–891.Link, Google Scholar
• [45] Vande Vate JH (1989) Linear programming brings marital bliss. Oper. Res. Lett. 8(3):147–153.Crossref, Google Scholar