{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:10Z","timestamp":1759639090023,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031221040"},{"type":"electronic","value":"9783031221057"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-22105-7_30","type":"book-chapter","created":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T02:36:12Z","timestamp":1672540572000},"page":"333-344","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Refined Computational Complexities of\u00a0Hospitals\/Residents Problem with\u00a0Regional Caps"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8863-6809","authenticated-orcid":false,"given":"Koki","family":"Hamada","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0369-1970","authenticated-orcid":false,"given":"Shuichi","family":"Miyazaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,1]]},"reference":[{"issue":"2","key":"30_CR1","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1257\/000282805774670167","volume":"95","author":"A Abdulkadiro\u011flu","year":"2005","unstructured":"Abdulkadiro\u011flu, A., Pathak, P.A., Roth, A.E.: The New York city high school match. Am. Econ. Rev. 95(2), 364\u2013367 (2005). https:\/\/doi.org\/10.1257\/000282805774670167","journal-title":"Am. Econ. Rev."},{"issue":"2","key":"30_CR2","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1257\/000282805774669637","volume":"95","author":"A Abdulkadiro\u011flu","year":"2005","unstructured":"Abdulkadiro\u011flu, A., Pathak, P.A., Roth, A.E., S\u00f6nmez, T.: The Boston public school match. Am. Econ. Rev. 95(2), 368\u2013371 (2005). https:\/\/doi.org\/10.1257\/000282805774669637","journal-title":"Am. Econ. Rev."},{"key":"30_CR3","unstructured":"Aziz, H., Baychkov, A., Bir\u00f3, P.: Summer internship matching with funding constraints. In: Seghrouchni, A.E.F., Sukthankar, G., An, B., Yorke-Smith, N. (eds.) Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems, pp. 97\u2013104 (2020). https:\/\/dl.acm.org\/doi\/10.5555\/3398761.3398778"},{"issue":"34\u201336","key":"30_CR4","doi-asserted-by":"publisher","first-page":"3136","DOI":"10.1016\/j.tcs.2010.05.005","volume":"411","author":"P Bir\u00f3","year":"2010","unstructured":"Bir\u00f3, P., Fleiner, T., Irving, R.W., Manlove, D.F.: The college admissions problem with lower and common quotas. Theor. Comput. Sci. 411(34\u201336), 3136\u20133153 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.05.005","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"30_CR5","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. Mon. 69(1), 9\u201315 (1962). https:\/\/doi.org\/10.1080\/00029890.1962.11989827","journal-title":"Am. Math. Mon."},{"issue":"3","key":"30_CR6","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). https:\/\/doi.org\/10.1016\/0166-218X(85)90074-5","journal-title":"Discrete Appl. Math."},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.artint.2016.02.002","volume":"235","author":"M Goto","year":"2016","unstructured":"Goto, M., Iwasaki, A., Kawasaki, Y., Kurata, R., Yasuda, Y., Yokoo, M.: Strategyproof matching with regional minimum and maximum quotas. Artif. Intell. 235, 40\u201357 (2016). https:\/\/doi.org\/10.1016\/j.artint.2016.02.002","journal-title":"Artif. Intell."},{"key":"30_CR8","series-title":"Foundations of Computing Series","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. Foundations of Computing Series, MIT Press, Cambridge (1989)"},{"issue":"1","key":"30_CR9","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). https:\/\/doi.org\/10.1007\/s00453-014-9951-z","journal-title":"Algorithmica"},{"key":"30_CR10","unstructured":"Hamada, K., Miyazaki, S.: Refined computational complexities of hospitals\/residents problem with regional caps. CoRR abs\/2107.03123 (2021). https:\/\/arxiv.org\/abs\/2107.03123"},{"key":"30_CR11","unstructured":"Kamada, Y., Kojima, F.: Improving efficiency in matching markets with regional caps: the case of the Japan residency matching program. Discussion papers, Stanford Institute for Economic Policy Research 1 (2010)"},{"issue":"3","key":"30_CR12","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1257\/aer.102.3.366","volume":"102","author":"Y Kamada","year":"2012","unstructured":"Kamada, Y., Kojima, F.: Stability and strategy-proofness for matching with constraints: a problem in the Japanese medical match and its solution. Am. Econ. Rev. 102(3), 366\u2013370 (2012). https:\/\/doi.org\/10.1257\/aer.102.3.366","journal-title":"Am. Econ. Rev."},{"issue":"1","key":"30_CR13","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1257\/aer.20101552","volume":"105","author":"Y Kamada","year":"2015","unstructured":"Kamada, Y., Kojima, F.: Efficient matching under distributional constraints: theory and applications. Am. Econ. Rev. 105(1), 67\u201399 (2015). https:\/\/doi.org\/10.1257\/aer.20101552","journal-title":"Am. Econ. Rev."},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.jet.2016.12.006","volume":"168","author":"Y Kamada","year":"2017","unstructured":"Kamada, Y., Kojima, F.: Stability concepts in matching under distributional constraints. J. Econ. Theory 168, 107\u2013142 (2017). https:\/\/doi.org\/10.1016\/j.jet.2016.12.006","journal-title":"J. Econ. Theory"},{"issue":"2","key":"30_CR15","doi-asserted-by":"publisher","first-page":"761","DOI":"10.3982\/TE2717","volume":"13","author":"Y Kamada","year":"2018","unstructured":"Kamada, Y., Kojima, F.: Stability and strategy-proofness for matching with constraints: a necessary and sufficient condition. Theor. Econ. 13(2), 761\u2013793 (2018). https:\/\/doi.org\/10.3982\/TE2717","journal-title":"Theor. Econ."},{"key":"30_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-3-030-57980-7_13","volume-title":"Algorithmic Game Theory","author":"P Krishnaa","year":"2020","unstructured":"Krishnaa, P., Limaye, G., Nasre, M., Nimbhorkar, P.: Envy-freeness and relaxed stability: hardness and approximation algorithms. In: Harks, T., Klimm, M. (eds.) SAGT 2020. LNCS, vol. 12283, pp. 193\u2013208. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-57980-7_13"},{"key":"30_CR17","doi-asserted-by":"publisher","unstructured":"Nasre, M., Nimbhorkar, P.: Popular matchings with lower quotas. In: Lokam, S.V., Ramanujam, R. (eds.) 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. LIPIcs, vol. 93, pp. 44:1\u201344:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2017.44","DOI":"10.4230\/LIPIcs.FSTTCS.2017.44"},{"issue":"6","key":"30_CR18","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). https:\/\/doi.org\/10.1086\/261272","journal-title":"J. Polit. Econ."},{"issue":"2","key":"30_CR19","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). https:\/\/doi.org\/10.2307\/1913160","journal-title":"Econometrica"},{"issue":"2","key":"30_CR20","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/s00453-018-0493-7","volume":"82","author":"Y Yokoi","year":"2020","unstructured":"Yokoi, Y.: Envy-free matchings with lower quotas. Algorithmica 82(2), 188\u2013211 (2020). https:\/\/doi.org\/10.1007\/s00453-018-0493-7","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22105-7_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,30]],"date-time":"2023-03-30T22:05:38Z","timestamp":1680213938000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22105-7_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031221040","9783031221057"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22105-7_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shenzhen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 October 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 October 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon-conference.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"101","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}