{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T01:36:31Z","timestamp":1784424991257,"version":"3.55.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T00:00:00Z","timestamp":1709337600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T00:00:00Z","timestamp":1709337600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Supported by the Department of Atomic Energy, Government  of India","award":["Project no. RTI4001"],"award-info":[{"award-number":["Project no. RTI4001"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We consider a matching problem in a bipartite graph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$G = (A \\cup B, E)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>G<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>A<\/mml:mi>\n                            <mml:mo>\u222a<\/mml:mo>\n                            <mml:mi>B<\/mml:mi>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>E<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    where vertices in\n                    <jats:italic>A<\/jats:italic>\n                    rank their neighbors in a strict order of preference while vertices in\n                    <jats:italic>B<\/jats:italic>\n                    are allowed to have\n                    <jats:italic>weak<\/jats:italic>\n                    rankings, i.e., ties are allowed in their rankings. Stable matchings always exist in\n                    <jats:italic>G<\/jats:italic>\n                    and are easy to find, however popular matchings need not exist in\n                    <jats:italic>G<\/jats:italic>\n                    and it is NP-complete to decide if one exists. This motivates the \u201capproximately popular\u201d matching problem. A well-known measure of approximate popularity is\n                    <jats:italic>low unpopularity factor<\/jats:italic>\n                    . We show that when each tie in\n                    <jats:italic>G<\/jats:italic>\n                    has length at most\u00a0\n                    <jats:italic>k<\/jats:italic>\n                    , there always exists a stable matching whose unpopularity factor is at most\n                    <jats:italic>k<\/jats:italic>\n                    and such a matching can be computed in polynomial time. Thus when ties have bounded length, there always exists a\n                    <jats:italic>near-popular<\/jats:italic>\n                    stable matching. This can be considered to be a generalization of G\u00e4rdenfors\u2019 result (1975) which showed that when rankings are strict, every stable matching is popular. We then extend our result to the hospitals\/residents setting, i.e., vertices in\n                    <jats:italic>B<\/jats:italic>\n                    have capacities. There are several applications where the size of the matching is its most important attribute. When ties are one-sided and of length at most\u00a0\n                    <jats:italic>k<\/jats:italic>\n                    , we show a polynomial time algorithm to find a maximum matching whose unpopularity factor\n                    <jats:italic>within<\/jats:italic>\n                    the set of maximum matchings is at most 2\n                    <jats:italic>k<\/jats:italic>\n                    .\n                  <\/jats:p>","DOI":"10.1007\/s00453-024-01215-6","type":"journal-article","created":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T06:02:32Z","timestamp":1709359352000},"page":"1888-1920","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Stable Matchings, One-Sided Ties, and Approximate Popularity"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2619-6606","authenticated-orcid":false,"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,3,2]]},"reference":[{"key":"1215_CR1","unstructured":"Bauckholt, F., Pashkovich, K., Sanit\u00e1, L.: On the approximability of the stable marriage problem with one-sided ties. (). arXiv:1805.05391"},{"key":"1215_CR2","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Hoefer, M., Huang, C.-C., Kavitha, T., Wagner, L.: Maintaining near-popular matchings. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP)(II), pp. 504\u2013515. (2015)","DOI":"10.1007\/978-3-662-47666-6_40"},{"key":"1215_CR3","doi-asserted-by":"crossref","unstructured":"Biro, P., Irving, R.W., Manlove, D.F.: Popular matchings in the marriage and roommates problems. In: Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC), pp. 97\u2013108. (2010)","DOI":"10.1007\/978-3-642-13073-1_10"},{"key":"1215_CR4","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)","journal-title":"Theoret. Comput. Sci."},{"issue":"7","key":"1215_CR5","doi-asserted-by":"publisher","first-page":"2738","DOI":"10.1007\/s00453-019-00553-0","volume":"81","author":"F Brandl","year":"2019","unstructured":"Brandl, F., Kavitha, T.: Two problems in max-size popular matchings. Algorithmica 81(7), 2738\u20132764 (2019)","journal-title":"Algorithmica"},{"key":"1215_CR6","unstructured":"Condorcet method. https:\/\/en.wikipedia.org\/wiki\/Condorcet_method"},{"key":"1215_CR7","unstructured":"Cseh, A.: Popular matchings. In: Endriss, U. (Ed.) Trends in Computational Social Choice (2017)"},{"issue":"4","key":"1215_CR8","doi-asserted-by":"publisher","first-page":"2348","DOI":"10.1137\/16M1076162","volume":"31","author":"A Cseh","year":"2017","unstructured":"Cseh, A., Huang, C.-C., Kavitha, T.: Popular matchings with two-sided preferences and one-sided ties. SIAM J. Discret. Math. 31(4), 2348\u20132377 (2017)","journal-title":"SIAM J. Discret. Math."},{"key":"1215_CR9","unstructured":"de Condorcet, N.: 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":"1215_CR10","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)","journal-title":"Can. J. Math."},{"issue":"1","key":"1215_CR11","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)","journal-title":"Math. Oper. Res."},{"key":"1215_CR12","doi-asserted-by":"crossref","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)","DOI":"10.1137\/1.9781611975482.173"},{"issue":"1","key":"1215_CR13","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)","journal-title":"Am. Math. Mon."},{"issue":"3","key":"1215_CR14","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. Discret. Appl. Math. 11(3), 223\u2013232 (1985)","journal-title":"Discret. Appl. Math."},{"key":"1215_CR15","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)","journal-title":"Behav. Sci."},{"issue":"2","key":"1215_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3442354","volume":"13","author":"S Gupta","year":"2021","unstructured":"Gupta, S., Misra, P., Saurabh, S., Zehavi, M.: Popular matching in roommates setting is NP-hard. ACM Trans. Comput. Theory 13(2), 1\u201320 (2021)","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1","key":"1215_CR17","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1137\/110852838","volume":"27","author":"C-C Huang","year":"2013","unstructured":"Huang, C.-C., Kavitha, T.: Near-popular matchings in the roommates problem. SIAM J. Discret. Math. 27(1), 43\u201362 (2013)","journal-title":"SIAM J. Discret. Math."},{"key":"1215_CR18","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."},{"issue":"1","key":"1215_CR19","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s10107-015-0923-0","volume":"154","author":"C-C Huang","year":"2015","unstructured":"Huang, C.-C., Kavitha, T.: Improved approximation algorithms for two variants of the stable marriage problem with ties. Math. Program. 154(1), 353\u2013380 (2015)","journal-title":"Math. Program."},{"key":"1215_CR20","doi-asserted-by":"crossref","unstructured":"Iwama, K., Miyazaki, S., Morita, Y., Manlove, D.: Stable marriage with incomplete lists and ties. In: Proceedings of the 26th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 443\u2013452. (1999)","DOI":"10.1007\/3-540-48523-6_41"},{"key":"1215_CR21","unstructured":"Iwama, K., Miyazaki, S., Yamauchi, N.: A 1.875-approximation algorithm for the stable marriage problem. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 288\u2013297. (2007)"},{"issue":"3","key":"1215_CR22","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/s00453-012-9699-2","volume":"68","author":"K Iwama","year":"2014","unstructured":"Iwama, K., Miyazaki, S., Yamauchi, N.: A 25\/17-approximation algorithm for the stable marriage problem with one-sided ties. Algorithmica 68(3), 758\u2013775 (2014)","journal-title":"Algorithmica"},{"issue":"1","key":"1215_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)","journal-title":"SIAM J. Comput."},{"key":"1215_CR24","unstructured":"Kavitha, T.: Stable matchings with one-sided ties and approximate popularity. In: Proceedings of the 42nd Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 22:1\u201322:17 (2022)"},{"issue":"1","key":"1215_CR25","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-009-9371-7","volume":"60","author":"Z Kir\u00e1ly","year":"2011","unstructured":"Kir\u00e1ly, Z.: Better and simpler approximation algorithms for the stable marriage problem. Algorithmica 60(1), 3\u201320 (2011)","journal-title":"Algorithmica"},{"key":"1215_CR26","doi-asserted-by":"crossref","unstructured":"Lam, C.-K., Plaxton, C.G.: A $$(1+1\/e)$$-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists. In: Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2823\u20132840 (2019)","DOI":"10.1137\/1.9781611975482.175"},{"issue":"3","key":"1215_CR27","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1007\/s00224-022-10072-1","volume":"66","author":"C-K Lam","year":"2022","unstructured":"Lam, C.-K., Plaxton, C.G.: Maximum stable matching with one-sided ties of bounded length. Theory Comput. Syst. 66(3), 645\u2013678 (2022)","journal-title":"Theory Comput. Syst."},{"key":"1215_CR28","unstructured":"Los\u00e1sz, L., Plummer, M.D.: Matching Theory. Mathematics Studies, vol. 121, North-Holland (1986)"},{"key":"1215_CR29","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10878-007-9133-x","volume":"16","author":"DF Manlove","year":"2008","unstructured":"Manlove, D.F., Irving, R.W.: Approximation algorithms for hard variants of the stable marriage and hospitals\/residents problems. J. Comb. Optim. 16, 279\u2013292 (2008)","journal-title":"J. Comb. Optim."},{"key":"1215_CR30","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","volume":"276","author":"DF Manlove","year":"2002","unstructured":"Manlove, D.F., Irving, R.W., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theoret. Comput. Sci. 276, 261\u2013279 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"1215_CR31","doi-asserted-by":"crossref","unstructured":"McCutchen, M.: The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences. In: Proceedings of the 8th Latin American Symposium on Theoretical Informatics (LATIN), pp. 593\u2013604 (2008)","DOI":"10.1007\/978-3-540-78773-0_51"},{"key":"1215_CR32","unstructured":"Pulleyblank, W.R.: Chapter 3, matchings and extensions. In: Graham, R.L., Gr\u00f6tschel, M., Lovasz, L. (eds.) The Handbook of Combinatorics, (1995)"},{"issue":"3","key":"1215_CR33","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/s00224-020-09978-5","volume":"65","author":"S Ruangwises","year":"2021","unstructured":"Ruangwises, S., Itoh, T.: Unpopularity factor in the marriage and roommates problems. Theory Comput. Syst. 65(3), 579\u2013592 (2021)","journal-title":"Theory Comput. Syst."},{"key":"1215_CR34","unstructured":"Soldner, M.: Optimization and measurement in humanitarian operations: addressing practical needs, Georgia Institute of Technology (2014). (PhD thesis)"},{"key":"1215_CR35","unstructured":"Trapp, A., Teytelboym, A., Martinello, A., Andersson, T., Ahani, N.: Placement optimization in refugee resettlement. Working paper , (2018)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01215-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01215-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01215-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T02:29:03Z","timestamp":1781231343000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01215-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,2]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["1215"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01215-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,2]]},"assertion":[{"value":"31 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2024","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 author has no competing financial or non-financial interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}