{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:48:25Z","timestamp":1750308505224,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["NI 369\/19"],"award-info":[{"award-number":["NI 369\/19"]}]},{"name":"DFG Research Training Group 2434 \u201cFacets of Complexity.\u201d"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n            In the NP-hard Hospital Residents problem with lower and upper quotas (\n            <jats:italic>\n              HR-Q\n              <jats:sub>L<\/jats:sub>\n              <jats:sup>U<\/jats:sup>\n            <\/jats:italic>\n            ), the goal is to find a stable matching of residents to hospitals where the number of residents matched to a hospital is either between its lower and upper quota or zero. We analyze this problem from a parameterized complexity perspective using several natural parameters such as the number of hospitals and the number of residents. Moreover, answering an open question of Bir\u00f3 et\u00a0al. [TCS 2010], we present an involved polynomial-time algorithm that finds a stable matching (if it exists) on instances with maximum lower quota two. Alongside\n            <jats:italic>\n              HR-Q\n              <jats:sub>L<\/jats:sub>\n              <jats:sup>U<\/jats:sup>\n            <\/jats:italic>\n            , we also consider two closely related models of independent interest, namely, the special case of\n            <jats:italic>\n              HR-Q\n              <jats:sub>L<\/jats:sub>\n              <jats:sup>U<\/jats:sup>\n            <\/jats:italic>\n            where each hospital has only a lower quota but no upper quota and the variation of\n            <jats:italic>\n              HR-Q\n              <jats:sub>L<\/jats:sub>\n              <jats:sup>U<\/jats:sup>\n            <\/jats:italic>\n            where hospitals do not have preferences over residents, which is also known as the House Allocation problem with lower and upper quotas. Last, we investigate the parameterized complexity of these three NP-hard problems when preferences may contain ties.\n          <\/jats:p>","DOI":"10.1145\/3546605","type":"journal-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T11:58:50Z","timestamp":1659614330000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Fine-grained View on Stable Many-to-one Matching Problems with Lower and Upper Quotas"],"prefix":"10.1145","volume":"10","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8779-0890","authenticated-orcid":false,"given":"Klaus","family":"Heeger","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2022,10,7]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1257\/000282805774670167"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.03.015"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-016-0085-x"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0252-6"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331717"},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1017\/CBO9781107446984.016","volume-title":"Handbook of Computational Social Choice","author":"Aziz Haris","year":"2016","unstructured":"Haris Aziz and Rahul Savani. 2016. Hedonic games. In Handbook of Computational Social Choice. Cambridge University Press, 356\u2013376."},{"issue":"49","key":"e_1_3_1_8_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. Electron. Colloquium Comput. Complex.49 (2003).","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.005"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_2"},{"key":"e_1_3_1_11_2","volume-title":"Student Admissions in Hungary as Gale and Shapley Envisaged","author":"Bir\u00f3 P\u00e9ter","year":"2008","unstructured":"P\u00e9ter Bir\u00f3. 2008. Student Admissions in Hungary as Gale and Shapley Envisaged. Technical Report TR-2008-291. University of Glasgow."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/970818.970828"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.12755"},{"key":"e_1_3_1_14_2","first-page":"44:1\u201344:14","volume-title":"Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC\u201919)","author":"Bredereck Robert","year":"2019","unstructured":"Robert Bredereck, Klaus Heeger, Du\u0161an Knop, and Rolf Niedermeier. 2019. Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters. In Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC\u201919). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 44:1\u201344:14."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2017.03.007"},{"key":"e_1_3_1_16_2","article-title":"Pareto optimal and popular house allocation with lower and upper quotas","author":"Cseh \u00c1gnes","year":"2021","unstructured":"\u00c1gnes Cseh, Tobias Friedrich, and Jannik Peters. 2021. Pareto optimal and popular house allocation with lower and upper quotas. arXiv preprint arXiv:2107.03801 [cs.GT] (2021).","journal-title":"arXiv preprint arXiv:2107.03801 [cs.GT]"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2014.03.004"},{"issue":"1","key":"e_1_3_1_20_2","first-page":"6:1\u20136:40","article-title":"Strategyproof matching with minimum quotas","volume":"4","author":"Fragiadakis Daniel","year":"2015","unstructured":"Daniel Fragiadakis, Atsushi Iwasaki, Peter Troyan, Suguru Ueda, and Makoto Yokoo. 2015. Strategyproof matching with minimum quotas. ACM Trans. Econ. Comput. 4, 1 (2015), 6:1\u20136:40.","journal-title":"ACM Trans. Econ. Comput."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.3982\/TE2195"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_3_1_23_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_1_24_2","article-title":"Maximally satisfying lower quotas in the hospitals\/residents problem with ties","author":"Goko Hiromichi","year":"2021","unstructured":"Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, and Yu Yokoi. 2021. Maximally satisfying lower quotas in the hospitals\/residents problem with ties. arXiv preprint arXiv:2105.03093 [cs.GT] (2021).","journal-title":"arXiv preprint arXiv:2105.03093 [cs.GT]"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9951-z"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2017.04.006"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90033-1"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.003"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.07.006"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-57980-7_13"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5297"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_3_1_35_2","article-title":"Envy-freeness and relaxed stability for lower-quotas: A parameterized perspective","author":"Limaye Girija","year":"2021","unstructured":"Girija Limaye. 2021. Envy-freeness and relaxed stability for lower-quotas: A parameterized perspective. arXiv preprint arXiv:2106.09917 [cs.DS] (2021).","journal-title":"arXiv preprint arXiv:2106.09917 [cs.DS]"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1142\/8591"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.5555\/3118785.3119248"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.07.004"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.08.017"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00636-y"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.econlet.2013.03.007"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/0404023"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00078-3"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1086\/261272"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.2307\/1913160"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-008-0117-6"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0493-7"},{"key":"e_1_3_1_48_2","volume-title":"Analysis of the Chinese College Admission System","author":"Zhang Haibo","year":"2010","unstructured":"Haibo Zhang. 2010. Analysis of the Chinese College Admission System. Ph.D. Dissertation. The University of Edinburgh."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3546605","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3546605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:44:02Z","timestamp":1750272242000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3546605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3546605"],"URL":"https:\/\/doi.org\/10.1145\/3546605","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"2021-02-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}