{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T08:12:28Z","timestamp":1777623148084,"version":"3.51.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T00:00:00Z","timestamp":1551052800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s00453-019-00553-0","type":"journal-article","created":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T07:35:49Z","timestamp":1551080149000},"page":"2738-2764","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Two Problems in Max-Size Popular Matchings"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3931-3931","authenticated-orcid":false,"given":"Florian","family":"Brandl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2619-6606","authenticated-orcid":false,"given":"Telikepalli","family":"Kavitha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,2,25]]},"reference":[{"issue":"4","key":"553_CR1","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/06067328X","volume":"37","author":"DJ Abraham","year":"2007","unstructured":"Abraham, D.J., Irving, R.W., Kavitha, T., Mehlhorn, K.: Popular matchings. SIAM J. Comput. 37(4), 1030\u20131045 (2007)","journal-title":"SIAM J. Comput."},{"key":"553_CR2","doi-asserted-by":"crossref","unstructured":"Askalidis, G., Immorlica, N., Kwanashie, A., Manlove, D., Pountourakis, E.: Socially Stable matchings in the hospitals\/residents problem. In: the 13th International Symposium on Algorithms and Data Structures (WADS), pp. 85\u201396 (2013)","DOI":"10.1007\/978-3-642-40104-6_8"},{"key":"553_CR3","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1287\/moor.13.4.619","volume":"13","author":"C Blair","year":"1988","unstructured":"Blair, C.: The lattice structure of the set of stable matchings with multiple partners. Math. Oper. Res. 13, 619\u2013628 (1988)","journal-title":"Math. Oper. Res."},{"key":"553_CR4","doi-asserted-by":"crossref","unstructured":"Biro, P., Irving, R.W., Manlove, D.F.: Popular matchings in the marriage and roommates problems. In: the 7th International Conference in Algorithms and Complexity (CIAC), pp. 97\u2013108 (2010)","DOI":"10.1007\/978-3-642-13073-1_10"},{"key":"553_CR5","unstructured":"Brandl, F., Kavitha, T.: Popular matchings with multiple partners. In: the 37th Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (2017)"},{"key":"553_CR6","unstructured":"Canadian Resident Matching Service. How the matching algorithm works. Web document available at \n                    http:\/\/carms.ca\/algorithm.htm"},{"key":"553_CR7","unstructured":"Condorcet, J.A.N.C.: Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. Imprimerie Royale, Paris (1785)"},{"key":"553_CR8","unstructured":"Cseh, \u00c1.: Popular matchings. In: Trends in Computational Social Choice, Edited by Ulle Endriss, COST (European Cooperation in Science and Technology), pp. 105\u2013122 (2017)"},{"key":"553_CR9","doi-asserted-by":"crossref","unstructured":"Cseh, \u00c1., Huang, C.-C., Kavitha, T.: Popular matchings with two-sided preferences and one-sided ties. In: the 42nd International Colloquium on Automata, Languages, and Programming (ICALP): Part I, pp. 367\u2013379 (2015)","DOI":"10.1007\/978-3-662-47672-7_30"},{"key":"553_CR10","doi-asserted-by":"crossref","unstructured":"Cseh, \u00c1., Kavitha, T.: Popular edges and dominant matchings. In: the 18th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 138\u2013151 (2016)","DOI":"10.1007\/978-3-319-33461-5_12"},{"key":"553_CR11","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Kavitha, T., Powers, V., Zhang, X.: Popular matchings and limits to tractability. In: The Conference is the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pp. 2790\u20132809 (2019)","DOI":"10.1137\/1.9781611975482.173"},{"issue":"1","key":"553_CR12","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.S.: College admissions and the stability of marriage. Am. Math. Month. 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Month."},{"issue":"3","key":"553_CR13","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(3), 223\u2013232 (1985)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"553_CR14","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(3), 166\u2013173 (1975)","journal-title":"Behav. Sci."},{"key":"553_CR15","doi-asserted-by":"crossref","unstructured":"Gupta, S., Misra, P., Saurabh, S., Zehavi, M.: Popular matching in roommates setting is NP-hard. The Conference is the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pp. 2810\u20132822 (2019)","DOI":"10.1137\/1.9781611975482.174"},{"key":"553_CR16","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"D Gusfield","year":"1989","unstructured":"Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Boston (1989)"},{"issue":"1","key":"553_CR17","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/s00453-014-9951-z","volume":"74","author":"K Hamada","year":"2016","unstructured":"Hamada, K., Iwama, K., Miyazaki, S.: The hospitals\/residents problem with lower quotas. Algorithmica 74(1), 440\u2013465 (2016)","journal-title":"Algorithmica"},{"key":"553_CR18","unstructured":"Hirakawa, M., Yamauchi, Y., Kijima, S., Yamashita, M.: On the structure of popular matchings in the stable marriage problem\u2014who can join a popular matching? In: The 3rd International Workshop on Matching Under Preferences (MATCH-UP) (2015)"},{"key":"553_CR19","doi-asserted-by":"crossref","unstructured":"Huang, C.-C.: Classified stable matching. In: the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1235\u20131253 (2010)","DOI":"10.1137\/1.9781611973075.99"},{"key":"553_CR20","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)","journal-title":"Inf. Comput."},{"key":"553_CR21","unstructured":"Huang, C.-C., Kavitha, T.: Popularity, self-duality, and mixed matchings. In: the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2294\u20132310 (2017)"},{"key":"553_CR22","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1016\/0196-6774(85)90033-1","volume":"6","author":"RW Irving","year":"1985","unstructured":"Irving, R.W.: An efficient algorithm for the stable roommates problem. J. Algorithms 6, 577\u2013595 (1985)","journal-title":"J. Algorithms"},{"key":"553_CR23","doi-asserted-by":"crossref","unstructured":"Irving, R.W., Manlove, D.F., Scott, S.: The hospitals\/residents problem with ties. In: the 7th Scandinavian Workshop on Algorithm Theory (SWAT), pp. 259\u2013271 (2000)","DOI":"10.1007\/3-540-44985-X_24"},{"key":"553_CR24","doi-asserted-by":"crossref","unstructured":"Irving, R.W., Manlove, D.F., Scott, S.: Strong stability in the hospitals\/residents problem. In the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 439\u2013450 (2003)","DOI":"10.1007\/3-540-36494-3_39"},{"issue":"1","key":"553_CR25","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)","journal-title":"SIAM J. Comput."},{"key":"553_CR26","unstructured":"Kavitha, T.: Popular half-integral matchings. In: the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 22.1\u201322.13 (2016)"},{"key":"553_CR27","unstructured":"Kavitha, T.: Max-size popular matchings and extensions. \n                    http:\/\/arxiv.org\/pdf\/1802.07440.pdf"},{"issue":"24","key":"553_CR28","doi-asserted-by":"publisher","first-page":"2679","DOI":"10.1016\/j.tcs.2010.03.028","volume":"412","author":"T Kavitha","year":"2011","unstructured":"Kavitha, T., Mestre, J., Nasre, M.: Popular mixed matchings. Theor. Comput. Sci. 412(24), 2679\u20132690 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"553_CR29","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1016\/j.endm.2017.07.030","volume":"61","author":"T Kir\u00e1ly","year":"2017","unstructured":"Kir\u00e1ly, T., M\u00e9sz\u00e1ros-Karkus, Zs: Finding strongly popular b-matchings in bipartite graphs. Electron. Notes Discrete Math. 61, 735\u2013741 (2017)","journal-title":"Electron. Notes Discrete Math."},{"key":"553_CR30","doi-asserted-by":"publisher","DOI":"10.1142\/8591","volume-title":"Algorithmics of Matching Under Preferences","author":"DF Manlove","year":"2013","unstructured":"Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific Publishing Company Incorporated, Singapore (2013)"},{"key":"553_CR31","first-page":"926","volume-title":"The Hospitals\/Residents Problem. Encyclopedia of Algorithms","author":"DF Manlove","year":"2015","unstructured":"Manlove, D.F.: The Hospitals\/Residents Problem. Encyclopedia of Algorithms, pp. 926\u2013930. Springer, Berlin (2015)"},{"key":"553_CR32","doi-asserted-by":"crossref","unstructured":"Nasre, M., Rawat, A.: Popularity in the generalized hospital residents setting. In: the 12th International Computer Science Symposium in Russia (CSR), pp. 245\u2013259 (2017)","DOI":"10.1007\/978-3-319-58747-9_22"},{"key":"553_CR33","unstructured":"National Resident Matching Program. Why the Match? Web document available at \n                    http:\/\/www.nrmp.org\/whythematch.pdf"},{"issue":"6","key":"553_CR34","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1086\/261272","volume":"92","author":"AE Roth","year":"1984","unstructured":"Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92(6), 991\u20131016 (1984)","journal-title":"J. Polit. Econ."},{"key":"553_CR35","doi-asserted-by":"publisher","first-page":"47","DOI":"10.2307\/1911460","volume":"53","author":"AE Roth","year":"1984","unstructured":"Roth, A.E.: Stability and polarization of interest in job matching. Econometrica 53, 47\u201357 (1984)","journal-title":"Econometrica"},{"issue":"2","key":"553_CR36","doi-asserted-by":"publisher","first-page":"425","DOI":"10.2307\/1913160","volume":"54","author":"AE Roth","year":"1986","unstructured":"Roth, A.E.: On the allocation of residents to rural hospitals: a general property of two-sided matching markets. Econometrica 54(2), 425\u2013427 (1986)","journal-title":"Econometrica"},{"key":"553_CR37","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0165-4896(98)00048-1","volume":"38","author":"M Sotomayor","year":"1999","unstructured":"Sotomayor, M.: Three remarks on the many-to-many stable matching problem. Math. Soc. Sci. 38, 55\u201370 (1999)","journal-title":"Math. Soc. Sci."},{"issue":"4","key":"553_CR38","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1137\/S0097539789169483","volume":"23","author":"A Subramanian","year":"1994","unstructured":"Subramanian, A.: A new approach to stable matching problems. SIAM J. Comput. 23(4), 671\u2013700 (1994)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"553_CR39","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)","journal-title":"Math. Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00553-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00553-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00553-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,24]],"date-time":"2020-02-24T19:15:42Z","timestamp":1582571742000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00553-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,25]]},"references-count":39,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["553"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00553-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,25]]},"assertion":[{"value":"24 May 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}