{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T22:29:02Z","timestamp":1773959342295,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T00:00:00Z","timestamp":1773878400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T00:00:00Z","timestamp":1773878400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"DOI":"10.13039\/501100001405","name":"Tata Institute of Fundamental Research","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001405","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s00453-025-01347-3","type":"journal-article","created":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T06:20:02Z","timestamp":1773901202000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Max-Utility Matchings with Popularity via Critical Vertices"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2619-6606","authenticated-orcid":false,"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,19]]},"reference":[{"issue":"3","key":"1347_CR1","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1257\/000282803322157061","volume":"93","author":"A Abdulkadiro\u011flu","year":"2003","unstructured":"Abdulkadiro\u011flu, A., S\u00f6nmez, T.: School choice: a mechanism design approach. Am. Econ. Rev. 93(3), 729\u2013747 (2003). https:\/\/doi.org\/10.1257\/000282803322157061","journal-title":"Am. Econ. Rev."},{"issue":"5","key":"1347_CR2","doi-asserted-by":"publisher","first-page":"1468","DOI":"10.1287\/opre.2020.2093","volume":"69","author":"N Ahani","year":"2021","unstructured":"Ahani, N., Andersson, T., Martinello, A., Trapp, A., Teytelboym, A.: Placement optimization in refugee resettlement. Oper. Res. 69(5), 1468\u20131486 (2021). https:\/\/doi.org\/10.1287\/opre.2020.2093","journal-title":"Oper. Res."},{"key":"1347_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01580600","volume":"60","author":"F Barahona","year":"1993","unstructured":"Barahona, F.: On cuts and matchings in planar graphs. Math. Program. 60, 53\u201368 (1993). https:\/\/doi.org\/10.1007\/BF01580600","journal-title":"Math. Program."},{"issue":"5","key":"1347_CR4","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1287\/inte.2019.1007","volume":"49","author":"S Baswana","year":"2019","unstructured":"Baswana, S., Chakrabarti, P.P., Chandran, S., Kanoria, Y., Patange, U.: Centralized admissions for engineering colleges in India. INFORMS J. Appl. Anal. 49(5), 338\u2013354 (2019). https:\/\/doi.org\/10.1287\/inte.2019.1007","journal-title":"INFORMS J. Appl. Anal."},{"key":"1347_CR5","doi-asserted-by":"publisher","first-page":"1828","DOI":"10.1016\/j.tcs.2010.02.003","volume":"411","author":"P Biro","year":"2010","unstructured":"Biro, P., Manlove, D.F., Mittal, S.: Size versus stability in the marriage problem. Theoret. Comput. Sci. 411, 1828\u20131841 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.02.003","journal-title":"Theoret. Comput. Sci."},{"key":"1347_CR6","unstructured":"Canadian Resident Matching\u00a0Service. How it works: the Match Algorithm. https:\/\/www.carms.ca\/the-match\/how-it-works\/"},{"key":"1347_CR7","unstructured":"Condorcet, M.: Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. L\u2019Imprimerie Royale (1785)"},{"key":"1347_CR8","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli,G.: Extended formulations in Combinatorial Optimization. https:\/\/www.andrew.cmu.edu\/user\/gc0v\/webpub\/ExtFor-Feb2010.pdf"},{"key":"1347_CR9","doi-asserted-by":"crossref","unstructured":"Cs\u00e1ji, G., Kir\u00e1ly, T., Takazawa, K., Yokoi, Y.: Popular maximum-utility matchings with matroid constraints. In: The 7th International Workshop on Matching Under Preferences (MATCH-UP). arXiv:abs\/2407.09798 (2024)","DOI":"10.1287\/moor.2024.0633"},{"key":"1347_CR10","first-page":"105","volume-title":"Trends in Computational Social Choice, Chapter 6","author":"A Cseh","year":"2017","unstructured":"Cseh, A.: Popular matchings. In: Endriss, U. (ed.) Trends in Computational Social Choice, Chapter 6, pp. 105\u2013122. AI Access Foundation (2017)"},{"key":"1347_CR11","doi-asserted-by":"publisher","first-page":"517","DOI":"10.4153\/CJM-1958-052-0","volume":"10","author":"AL Dulmage","year":"1958","unstructured":"Dulmage, A.L., Mendelsohn, N.S.: Coverings of bipartite graphs. Can. J. Math. 10, 517\u2013534 (1958). https:\/\/doi.org\/10.4153\/CJM-1958-052-0","journal-title":"Can. J. Math."},{"issue":"3\u20134","key":"1347_CR12","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s00182-007-0081-6","volume":"36","author":"K Eriksson","year":"2008","unstructured":"Eriksson, K., H\u00e4ggstr\u00f6m, O.: Instability of matchings in decentralized markets with various preference orders. Math. Program. 36(3\u20134), 409\u2013420 (2008). https:\/\/doi.org\/10.1007\/s00182-007-0081-6","journal-title":"Math. Program."},{"issue":"1","key":"1347_CR13","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1287\/moor.2021.1139","volume":"47","author":"Y Faenza","year":"2022","unstructured":"Faenza, Y., Kavitha, T.: Quasi-popular matchings, optimality, and extended formulations. Math. Oper. Res. 47(1), 427\u2013457 (2022). https:\/\/doi.org\/10.1287\/moor.2021.1139","journal-title":"Math. Oper. Res."},{"key":"1347_CR14","doi-asserted-by":"publisher","unstructured":"Faenza, Y., Kavitha, T., Powers, V., Zhang, X.: Popular matchings and limits to tractability. In: Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2790\u20132809 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.173","DOI":"10.1137\/1.9781611975482.173"},{"issue":"6","key":"1347_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2841226","volume":"4","author":"D Fragiadakis","year":"2015","unstructured":"Fragiadakis, D., Iwasaki, A., Troyan, P., Ueda, S., Yokoo, M.: Strategy proof matching with minimum quotas. ACM Trans. Econ. Comput. 4(6), 1\u201340 (2015). https:\/\/doi.org\/10.1145\/2841226","journal-title":"ACM Trans. Econ. Comput."},{"issue":"1","key":"1347_CR16","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9\u201315 (1962). https:\/\/doi.org\/10.1080\/00029890.1962.11989827","journal-title":"Am. Math. Mon."},{"key":"1347_CR17","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0166-218X(85)90074-5","volume":"11","author":"D Gale","year":"1985","unstructured":"Gale, D., Sotomayor, M.: Some remarks on the stable matching problem. Discrete Appl. Math. 11, 223\u2013232 (1985). https:\/\/doi.org\/10.1016\/0166-218X(85)90074-5","journal-title":"Discrete Appl. Math."},{"key":"1347_CR18","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/bs.3830200304","volume":"20","author":"P G\u00e4rdenfors","year":"1975","unstructured":"G\u00e4rdenfors, P.: Match making: assignments based on bilateral preferences. Behav. Sci. 20, 166\u2013173 (1975). https:\/\/doi.org\/10.1002\/bs.3830200304","journal-title":"Behav. Sci."},{"key":"1347_CR19","unstructured":"Goemans, M.: Combinatorial optimization. https:\/\/math.mit.edu\/~goemans\/18453S17\/polyhedral.pdf (2017)"},{"key":"1347_CR20","unstructured":"Hirakawa, M., Yamauchi, Y., Kijima, S., Yamashita, M.: 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)"},{"key":"1347_CR21","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.ic.2012.10.012","volume":"222","author":"C-C Huang","year":"2013","unstructured":"Huang, C.-C., Kavitha, T.: Popular matchings in the stable marriage problem. Inf. Comput. 222, 180\u2013194 (2013). https:\/\/doi.org\/10.1016\/j.ic.2012.10.012","journal-title":"Inf. Comput."},{"issue":"3","key":"1347_CR22","doi-asserted-by":"publisher","first-page":"1361","DOI":"10.1137\/110839813","volume":"26","author":"V Kaibel","year":"2012","unstructured":"Kaibel, V., Pashkovich, K., Theist, D.O.: Symmetry matters for sizes of extended formulations. SIAM J. Discrete Math. 26(3), 1361\u20131382 (2012). https:\/\/doi.org\/10.1137\/110839813","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1347_CR23","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1137\/120902562","volume":"43","author":"T Kavitha","year":"2014","unstructured":"Kavitha, T.: A size-popularity tradeoff in the stable marriage problem. SIAM J. Comput. 43(1), 52\u201371 (2014). https:\/\/doi.org\/10.1137\/120902562","journal-title":"SIAM J. Comput."},{"key":"1347_CR24","doi-asserted-by":"publisher","unstructured":"Kavitha, T.: Matchings, critical nodes, and popular solutions. In: Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, pp. 1\u201319 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2021.25","DOI":"10.4230\/LIPIcs.FSTTCS.2021.25"},{"issue":"2","key":"1347_CR25","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1137\/24M163596X","volume":"39","author":"T Kavitha","year":"2025","unstructured":"Kavitha, T.: Matchings, relaxed popularity, and optimality. SIAM J. Discrete Math. 39(2), 881\u2013911 (2025). https:\/\/doi.org\/10.1137\/24M163596X","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"1347_CR26","doi-asserted-by":"publisher","first-page":"1202","DOI":"10.1137\/22M1523248","volume":"38","author":"T Kavitha","year":"2024","unstructured":"Kavitha, T.: Maximum matchings and popularity. SIAM J. Discrete Math. 38(2), 1202\u20131221 (2024). https:\/\/doi.org\/10.1137\/22M1523248","journal-title":"SIAM J. Discrete Math."},{"key":"1347_CR27","doi-asserted-by":"publisher","unstructured":"Kavitha, T.: Popular solutions for optimal matchings. In: Proceedings of the 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG, pp. 297\u2013311 (2024). https:\/\/doi.org\/10.1007\/978-3-031-75409-8_21","DOI":"10.1007\/978-3-031-75409-8_21"},{"issue":"1","key":"1347_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10878-022-00963-x","volume":"45","author":"P Krishnaa","year":"2023","unstructured":"Krishnaa, P., Limaye, G., Nasre, M., Nimbhorkar, P.: Envy-freeness and relaxed stability: hardness and approximation algorithms. J. Combin. Optim. 45(1), 1\u201330 (2023). https:\/\/doi.org\/10.1007\/s10878-022-00963-x","journal-title":"J. Combin. Optim."},{"key":"1347_CR29","unstructured":"Los\u00e1sz, L., Plummer, M.D.: Matching theory. In: Mathematics Studies, vol. 121. North-Holland (1986)"},{"key":"1347_CR30","unstructured":"Mathieu, C.: Stable matching in practice. In: The 26th Annual European Symposium on Algorithms (ESA), Keynote Talk (2018)"},{"key":"1347_CR31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511605864","volume-title":"A Unified Theory of Voting: Directional and Proximity Spatial Models","author":"S Merrill","year":"1999","unstructured":"Merrill, S., Grofman, B.: A Unified Theory of Voting: Directional and Proximity Spatial Models. Cambridge University Press (1999). https:\/\/doi.org\/10.1017\/CBO9780511605864"},{"key":"1347_CR32","doi-asserted-by":"publisher","unstructured":"Nasre, M., Nimbhorkar, P.: Popular matchings with lower quotas. In: Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, pp. 1\u201315 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2017.44","DOI":"10.4230\/LIPIcs.FSTTCS.2017.44"},{"key":"1347_CR33","doi-asserted-by":"publisher","unstructured":"Nasre, M., Nimbhorkar, P., Ranjan, K., Sarkar, A.: Popular matchings in the hospital-residents problem with two-sided lower quotas. In: Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS, pp. 1\u201321 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2021.30","DOI":"10.4230\/LIPIcs.FSTTCS.2021.30"},{"key":"1347_CR34","doi-asserted-by":"publisher","first-page":"114281","DOI":"10.1016\/j.tcs.2023.114281","volume":"982","author":"M Nasre","year":"2024","unstructured":"Nasre, M., Nimbhorkar, P., Ranjan, K., Sarkar, A.: Popular critical matchings in the many-to-many setting. Theoret. Comput. Sci. 982, 114281 (2024). https:\/\/doi.org\/10.1016\/j.tcs.2023.114281","journal-title":"Theoret. Comput. Sci."},{"key":"1347_CR35","unstructured":"Program, N.R.M.: The Match. https:\/\/www.nrmp.org\/about\/"},{"key":"1347_CR36","volume-title":"The Handbook of Combinatorics","author":"WR Pulleyblank","year":"1995","unstructured":"Pulleyblank, W.R.: Chapter 3, Matchings and extensions. In: Graham, R.L., Gr\u00f6tschel, M., Lovasz, L. (eds.) The Handbook of Combinatorics. Elsevier (1995)"},{"key":"1347_CR37","unstructured":"Robards, P.A.: Applying the two-sided matching processes to the United States Navy enlisted assignment process. Master\u2019s Thesis, Naval Postgraduate School, Monterey, Canada (2001)"},{"issue":"2","key":"1347_CR38","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1086\/262074","volume":"105","author":"AE Roth","year":"1997","unstructured":"Roth, A.E., Xing, X.: Turnaround time and bottlenecks in market clearing: decentralized matching in the market for clinical psychologists. J. Polit. Econ. 105(2), 284\u2013329 (1997). https:\/\/doi.org\/10.1086\/262074","journal-title":"J. Polit. Econ."},{"key":"1347_CR39","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01586041","volume":"54","author":"UG Rothblum","year":"1992","unstructured":"Rothblum, U.G.: Characterization of stable matchings as extreme points of a polytope. Math. Program. 54, 57\u201367 (1992). https:\/\/doi.org\/10.1007\/BF01586041","journal-title":"Math. Program."},{"issue":"6","key":"1347_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3127497","volume":"64","author":"T Rothvoss","year":"2017","unstructured":"Rothvoss, T.: The matching polytope has exponential extension complexity. J. ACM (JACM) 64(6), 1\u201319 (2017). https:\/\/doi.org\/10.1145\/3127497","journal-title":"J. ACM (JACM)"},{"key":"1347_CR41","unstructured":"Schrijver, A.: Combinatorial optimization\u2014polyhedra and efficiency. In: Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003). https:\/\/homepages.cwi.nl\/~lex\/files\/book.pdf"},{"key":"1347_CR42","unstructured":"Soldner, M.: Optimization and measurement in humanitarian operations: Addressing practical needs. PhD thesis, Georgia Institute of Technology (2014)"},{"issue":"4","key":"1347_CR43","doi-asserted-by":"publisher","first-page":"874","DOI":"10.1287\/moor.23.4.874","volume":"23","author":"C-P Teo","year":"1998","unstructured":"Teo, C.-P., Sethuraman, J.: The geometry of fractional stable matchings and its applications. Math. Oper. Res. 23(4), 874\u2013891 (1998). https:\/\/doi.org\/10.1287\/moor.23.4.874","journal-title":"Math. Oper. Res."},{"key":"1347_CR44","unstructured":"Yang, W., Giampapa, J.A., Sycara, K.: Two-sided matching for the US Navy detailing process with market complication. Technical Report CMU-R1-TR-03-49, Robotics Institute, Carnegie Mellon University (2003). https:\/\/www.ri.cmu.edu\/pub_files\/pub4\/yang_wei_2003_2\/yang_wei_2003_2.pdf"},{"issue":"2","key":"1347_CR45","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/s00453-018-0493-7","volume":"82","author":"Y Yokoi","year":"2020","unstructured":"Yokoi, Y.: Envy-free matchings with lower quotas. Algorithmica 82(2), 188\u2013211 (2020). https:\/\/doi.org\/10.1007\/s00453-018-0493-7","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01347-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01347-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01347-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T19:01:25Z","timestamp":1773946885000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01347-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,19]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1347"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01347-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,19]]},"assertion":[{"value":"6 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"30"}}