{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:34Z","timestamp":1750309294820,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,1,22]],"date-time":"2024-01-22T00:00:00Z","timestamp":1705881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"\n Let\n G<\/jats:italic>\n =\n (A \u222a B, E)<\/jats:italic>\n be a bipartite graph where the set\n A<\/jats:italic>\n consists of agents or main players and the set\n B<\/jats:italic>\n consists of jobs or secondary players. Every vertex in\n A<\/jats:italic>\n \u222a\n B<\/jats:italic>\n has a strict ranking of its neighbors. A matching\n M<\/jats:italic>\n is\n popular<\/jats:italic>\n if for any matching\n N<\/jats:italic>\n , the number of vertices that prefer\n M<\/jats:italic>\n to\n N<\/jats:italic>\n is at least the number that prefer\n N<\/jats:italic>\n to\n M<\/jats:italic>\n . Popular matchings always exist in\n G<\/jats:italic>\n since every stable matching is popular. A matching\n M<\/jats:italic>\n is\n \n A<\/jats:italic>\n -popular\n <\/jats:italic>\n if for any matching\n N<\/jats:italic>\n , the number of\n agents<\/jats:italic>\n (i.e., vertices in\n A<\/jats:italic>\n ) that prefer\n M<\/jats:italic>\n to\n N<\/jats:italic>\n is at least the number of agents that prefer\n N<\/jats:italic>\n to\n M<\/jats:italic>\n . Unlike popular matchings,\n A<\/jats:italic>\n -popular matchings need not exist in a given instance\n G<\/jats:italic>\n and there is a simple linear time algorithm to decide if\n G<\/jats:italic>\n admits an\n A<\/jats:italic>\n -popular matching and compute one, if so.\n <\/jats:p>\n \n We consider the problem of deciding if\n G<\/jats:italic>\n admits a matching that is both popular and\n A<\/jats:italic>\n -popular and finding one, if so. We call such matchings\n fully popular<\/jats:italic>\n . A fully popular matching is useful when\n A<\/jats:italic>\n is the more important side\u2014so along with overall popularity, we would like to maintain \u201cpopularity within\u00a0the\u00a0set\u00a0\n A<\/jats:italic>\n \u201d. A fully popular matching is not necessarily a min-size\/max-size popular matching and all known polynomial-time algorithms for popular matching problems compute either min-size or max-size popular matchings. Here we show a linear time algorithm for the fully popular matching problem, thus our result shows a new tractable subclass of popular matchings.\n <\/jats:p>","DOI":"10.1145\/3638764","type":"journal-article","created":{"date-parts":[[2023,12,27]],"date-time":"2023-12-27T22:10:40Z","timestamp":1703715040000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Popular Matchings with One-Sided Bias"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2619-6606","authenticated-orcid":false,"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[{"name":"Tata Institute of Fundamental Research, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,22]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1257\/000282803322157061"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/06067328X"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/inte.2019.1007"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13073-1_10"},{"key":"e_1_3_2_6_2","unstructured":"Canadian Resident Matching Service. 1969. How it Works: The Match Algorithm. (1969). http:\/\/carms.ca\/the-match\/how-it-works\/"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1076162"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1183-y"},{"key":"e_1_3_2_9_2","volume-title":"Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix","author":"Condorcet Nicolas de","year":"1785","unstructured":"Nicolas de Condorcet. 1785. Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. L\u2019Imprimerie Royale."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1139"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.173"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90074-5"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/bs.3830200304"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/68392"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.012"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2020.1063"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.003"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/120902562"},{"key":"e_1_3_2_20_2","first-page":"22:1\u201322:13","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Kavitha Telikepalli","year":"2016","unstructured":"Telikepalli Kavitha. 2016. Popular half-integral matchings. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP). 22:1\u201322:13."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.03.028"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2556951"},{"key":"e_1_3_2_23_2","unstructured":"National Resident Matching Program. 1952. The Match. (1952). http:\/\/www.nrmp.org"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.11.008"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3638764","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3638764","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:33Z","timestamp":1750291413000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3638764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,22]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3638764"],"URL":"https:\/\/doi.org\/10.1145\/3638764","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,1,22]]},"assertion":[{"value":"2022-10-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}