{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T17:20:25Z","timestamp":1762017625619,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>In practical applications, algorithms for the classic version of the hospitals residents problem (the many-one version of the stable marriage problem) may have to be extended to accommodate the needs of couples who wish to be allocated to (geographically) compatible places. Such an extension has been in operation in the National Resident Matching Problem (NRMP) matching scheme in the United States for a number of years. In this setting, a stable matching need not exist, and it is an NP-complete problem to decide if one does. However, the only previous empirical study in this context (focused on the NRMP algorithm), together with information from NRMP, suggest that, in practice, stable matchings do exist and that an appropriate heuristic can be used to find such a matching.<\/jats:p>\n          <jats:p>The study presented here was motivated by the recent decision to accommodate couples in the Scottish Foundation Allocation Scheme (SFAS), the Scottish equivalent of the NRMP. Here, the problem is a special case, since hospital preferences are derived from a \u201cmaster list\u201d of resident scores, but we show that the existence problem remains NP-complete in this case. We describe the algorithm used in SFAS and contrast it with a version of the algorithm that forms the basis of the NRMP approach. We also propose a third simpler algorithm based on satisfying blocking pairs, and an FPT algorithm when the number of couples is viewed as a parameter. We present an empirical study of the performance of a number of variants of these algorithms using a range of datasets. The results indicate that, not surprisingly, increasing the ratio of couples to single applicants typically makes it harder to find a stable matching (and, by inference, less likely that a stable matching exists). However, the likelihood of finding a stable matching is very high for realistic values of this ratio, and especially so for particular variants of the algorithms.<\/jats:p>","DOI":"10.1145\/1963190.1970372","type":"journal-article","created":{"date-parts":[[2012,10,15]],"date-time":"2012-10-15T19:22:23Z","timestamp":1350328943000},"source":"Crossref","is-referenced-by-count":27,"title":["Stable matching with couples"],"prefix":"10.1145","volume":"16","author":[{"given":"P\u00e9ter","family":"Bir\u00f3","sequence":"first","affiliation":[{"name":"Hungarian Academy of Sciences, Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert W.","family":"Irving","sequence":"additional","affiliation":[{"name":"University of Glasgow, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ildik\u00f3","family":"Schlotter","sequence":"additional","affiliation":[{"name":"Budapest University of Technology and Economics"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,5,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(96)89151-7"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Bir\u00f3 P. Irving R. and Schlotter I. 2011. Stable matching with couples\u2014theory and practice. Tech. rep. no. TR-2011-324 University of Glasgow School of Computing Science.  Bir\u00f3 P. Irving R. and Schlotter I. 2011. Stable matching with couples\u2014theory and practice. Tech. rep. no. TR-2011-324 University of Glasgow School of Computing Science.","DOI":"10.1145\/1963190.1970372"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(80)90051-X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.01.002"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.04.006"},{"key":"e_1_2_1_7_1","first-page":"175","article-title":"Some things couples always wanted to know about stable matchings (but were afraid to ask)","volume":"11","author":"Klaus B.","year":"2007","journal-title":"Rev. Econ. Des."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2009.06.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Kojima F. Pathak P. and Roth A. 2010. Matching with couples: stability and incentives in large markets. Working paper.  Kojima F. Pathak P. and Roth A. 2010. Matching with couples: stability and incentives in large markets. Working paper.","DOI":"10.3386\/w16028"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.07.004"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9257-2"},{"key":"e_1_2_1_12_1","unstructured":"National Resident Matching Program. 2011. http:\/\/www.nrmp.org\/.  National Resident Matching Program. 2011. http:\/\/www.nrmp.org\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90007-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-008-0117-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1086\/261272"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.89.4.748"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/2938326"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0207"},{"key":"e_1_2_1_19_1","unstructured":"Scottish Foundation Allocation Scheme. 2011. http:\/\/www.nes.scot.nhs.uk\/sfas\/.  Scottish Foundation Allocation Scheme. 2011. http:\/\/www.nes.scot.nhs.uk\/sfas\/."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1963190.1970372","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1963190.1970372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:02Z","timestamp":1750278362000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1963190.1970372"}},"subtitle":["An empirical study"],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":19,"alternative-id":["10.1145\/1963190.1970372"],"URL":"https:\/\/doi.org\/10.1145\/1963190.1970372","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2011,5]]}}}