{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T14:36:31Z","timestamp":1787236591281,"version":"build-2736575974"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,15]],"date-time":"2024-04-15T00:00:00Z","timestamp":1713139200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["MaMu (NI 369\/19), ComSoc-MPMS (NI 369\/22)"],"award-info":[{"award-number":["MaMu (NI 369\/19), ComSoc-MPMS (NI 369\/22)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DFG","award":["DiPa (NI 369\/21)"],"award-info":[{"award-number":["DiPa (NI 369\/21)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>We analyze the (parameterized) computational complexity of \u201cfair\u201d variants of bipartite many-to-one matching, where each vertex from the \u201cleft\u201d side is matched to exactly one vertex and each vertex from the \u201cright\u201d side may be matched to multiple vertices. We want to find a \u201cfair\u201d matching, in which each vertex from the right side is matched to a \u201cfair\u201d set of vertices. Assuming that each vertex from the left side has one color modeling its \u201cattribute\u201d, we study two fairness criteria. For instance, in one of them, we deem a vertex set fair if for any two colors, the difference between the numbers of their occurrences does not exceed a given threshold. Fairness is, for instance, relevant when finding many-to-one matchings between students and colleges, voters and constituencies, and applicants and firms. Here colors may model sociodemographic attributes, party memberships, and qualifications, respectively.<\/jats:p>\n                  <jats:p>We show that finding a fair many-to-one matching is NP-hard even for three colors and maximum degree five. Our main contribution is the design of fixed-parameter tractable algorithms with respect to the number of vertices on the right side. Our algorithms make use of a variety of techniques including color coding. At the core lie integer linear programs encoding Hall like conditions. We establish the correctness of our integer programs, based on Frank\u2019s separation theorem [Frank, Discrete Math. 1982]. We further obtain complete complexity dichotomies regarding the number of colors and the maximum degree of each side.<\/jats:p>","DOI":"10.1145\/3649220","type":"journal-article","created":{"date-parts":[[2024,2,24]],"date-time":"2024-02-24T04:17:27Z","timestamp":1708748247000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The Complexity of Finding Fair Many-to-One Matchings"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5102-449X","authenticated-orcid":false,"given":"Niclas","family":"Boehmer","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8684-0611","authenticated-orcid":false,"given":"Tomohiro","family":"Koana","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,15]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"3","volume-title":"Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI\u201920)","author":"Ahmadi Saba","year":"2020","unstructured":"Saba Ahmadi, Faez Ahmed, John P. Dickerson, Mark Fuge, and Samir Khuller. 2020. An algorithm for multi-attribute diverse matching. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI\u201920). ijcai.org, 3\u20139."},{"key":"e_1_3_3_3_2","first-page":"4195","volume-title":"Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS\u201920)","author":"Ahmadian Sara","year":"2020","unstructured":"Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. 2020. Fair correlation clustering. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS\u201920). PMLR, 4195\u20134205."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1115\/1.4046998"},{"key":"e_1_3_3_5_2","first-page":"35","volume-title":"Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI\u201917)","author":"Ahmed Faez","year":"2017","unstructured":"Faez Ahmed, John P. Dickerson, and Mark Fuge. 2017. Diverse weighted bipartite b-matching. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI\u201917). ijcai.org, 35\u201341."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_3_7_2","article-title":"Maximizing coverage while ensuring fairness: A tale of conflicting objective","volume":"2007","author":"Asudeh Abolfazl","year":"2020","unstructured":"Abolfazl Asudeh, Tanya Y. Berger-Wolf, Bhaskar DasGupta, and Anastasios Sidiropoulos. 2020. Maximizing coverage while ensuring fairness: A tale of conflicting objective. CoRR abs\/2007.08069 (2020).","journal-title":"CoRR"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331717"},{"key":"e_1_3_3_9_2","volume-title":"Poor Economics: A Radical Rethinking of the Way to Fight Global Poverty","author":"Banerjee Abhijit V.","year":"2011","unstructured":"Abhijit V. Banerjee and Esther Duflo. 2011. Poor Economics: A Radical Rethinking of the Way to Fight Global Poverty. Public Affairs."},{"key":"e_1_3_3_10_2","doi-asserted-by":"crossref","unstructured":"Abhijit V. Banerjee and Rohini Pande. 2007. Parochial politics: Ethnic preferences and politician corruption. (2007).","DOI":"10.2139\/ssrn.976548"},{"key":"e_1_3_3_11_2","article-title":"Finding balance-fair short paths in graphs","volume":"2203","author":"Bentert Matthias","year":"2022","unstructured":"Matthias Bentert, Leon Kellerhals, and Rolf Niedermeier. 2022. Finding balance-fair short paths in graphs. CoRR abs\/2203.17132 (2022). arXiv:2203.17132https:\/\/arxiv.org\/abs\/2203.17132","journal-title":"CoRR"},{"issue":"49","key":"e_1_3_3_12_2","article-title":"Approximation hardness of short symmetric instances of MAX-3SAT","author":"Berman Piotr","year":"2003","unstructured":"Piotr Berman, Marek Karpinski, and Alex D. Scott. 2003. Approximation hardness of short symmetric instances of MAX-3SAT. ECCC49 (2003).","journal-title":"ECCC"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2016.03.003"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/3535850.3536030"},{"key":"e_1_3_3_15_2","first-page":"146","volume-title":"Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI\u201920)","author":"Chen Jiehua","year":"2020","unstructured":"Jiehua Chen, Robert Ganian, and Thekla Hamm. 2020. Stable matchings with diversity constraints: Affirmative action is beyond NP. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI\u201920). ijcai.org, 146\u2013152."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90068-8"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_3_18_2","first-page":"1877","volume-title":"Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI\u201919)","author":"Dickerson John P.","year":"2019","unstructured":"John P. Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. 2019. Balancing relevance and diversity in online bipartite matching via submodularity. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI\u201919). AAAI Press, 1877\u20131884."},{"issue":"3","key":"e_1_3_3_19_2","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1093\/qmath\/27.3.339","article-title":"Matroids and submodular functions","volume":"27","author":"Dunstan F. D. J.","year":"1976","unstructured":"F. D. J. Dunstan. 1976. Matroids and submodular functions. The Quarterly Journal of Mathematics 27, 3 (1976), 339\u2013348.","journal-title":"The Quarterly Journal of Mathematics"},{"key":"e_1_3_3_20_2","unstructured":"EdBuild. 2019. Non-white school districts get $23 billion less than white districts despite serving the same number of students. (2019)."},{"key":"e_1_3_3_21_2","first-page":"97","article-title":"An algorithm for submodular functions on graphs","volume":"16","author":"Frank Andr\u00e1s","year":"1982","unstructured":"Andr\u00e1s Frank. 1982. An algorithm for submodular functions on graphs. Discrete Math. 16 (1982), 97\u2013120.","journal-title":"Discrete Math."},{"key":"e_1_3_3_22_2","volume-title":"Connections in Combinatorial Optimization","author":"Frank Andr\u00e1s","year":"2011","unstructured":"Andr\u00e1s Frank. 2011. Connections in Combinatorial Optimization. Vol. 38. Oxford University Press Oxford."},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1007\/978-3-030-83508-8_30","volume-title":"Proceedings of the 17th International Symposium on Algorithms and Data Structures (WADS\u201921)","author":"Friggstad Zachary","year":"2021","unstructured":"Zachary Friggstad and Ramin Mousavi. 2021. Fair correlation clustering with global and local guarantees. In Proceedings of the 17th International Symposium on Algorithms and Data Structures (WADS\u201921). Springer, 414\u2013427."},{"key":"e_1_3_3_24_2","article-title":"Modification-fair cluster editing","volume":"2112","author":"Froese Vincent","year":"2021","unstructured":"Vincent Froese, Leon Kellerhals, and Rolf Niedermeier. 2021. Modification-fair cluster editing. CoRR abs\/2112.03183 (2021). arXiv:2112.03183https:\/\/arxiv.org\/abs\/2112.03183Accepted for the Proceedings of AAAI 2022.","journal-title":"CoRR"},{"key":"e_1_3_3_25_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.3982\/TE1135"},{"key":"e_1_3_3_27_2","first-page":"58","article-title":"On representatives of subsets","author":"Hall Philip","year":"1987","unstructured":"Philip Hall. 1987. On representatives of subsets. Classic Papers in Combinatorics (1987), 58\u201362.","journal-title":"Classic Papers in Combinatorics"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2005.01.003"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873700"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"e_1_3_3_31_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler Eugene L.","year":"2001","unstructured":"Eugene L. Lawler. 2001. Combinatorial Optimization: Networks and Matroids. Courier Corporation."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1909"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/3463952.3464069"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/3398761.3398912"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649220","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:17:47Z","timestamp":1750281467000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,15]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3649220"],"URL":"https:\/\/doi.org\/10.1145\/3649220","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,15]]},"assertion":[{"value":"2023-01-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-18","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}