{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T07:39:02Z","timestamp":1773733142154,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/E011993\/1"],"award-info":[{"award-number":["EP\/E011993\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>When ties and incomplete preference lists are permitted in the stable marriage and hospitals\/residents problems, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-hard, even under very severe restrictions on the number, size, and position of ties. In this article, we present two new heuristics for finding large stable matchings in variants of these problems in which ties are on one side only. We describe an empirical study involving these heuristics and the best existing approximation algorithm for this problem. Our results indicate that all three of these algorithms perform significantly better than naive tie-breaking algorithms when applied to real-world and randomly-generated data sets and that one of the new heuristics fares slightly better than the other algorithms, in most cases. This study, and these particular problem variants, are motivated by important applications in large-scale centralized matching schemes.<\/jats:p>","DOI":"10.1145\/1498698.1537595","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":22,"title":["Finding large stable matchings"],"prefix":"10.1145","volume":"14","author":[{"given":"Robert W.","family":"Irving","sequence":"first","affiliation":[{"name":"University of Glasgow, Glasgow, Scotland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David F.","family":"Manlove","sequence":"additional","affiliation":[{"name":"University of Glasgow, Glasgow, Scotland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1257\/000282805774670167"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Abdulkadiro\u01e7lu A. Pathak P. Roth A. and S\u00f6onmez T. 2006. Changing the Boston school-choice mechanism. NBER working paper 11965.  Abdulkadiro\u01e7lu A. Pathak P. Roth A. and S\u00f6onmez T. 2006. Changing the Boston school-choice mechanism. NBER working paper 11965.","DOI":"10.3386\/w11965"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.03.011"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 18th International Conference on Game Theory.","author":"Bir\u00f3 P.","year":"2007","unstructured":"Bir\u00f3 , P. 2007 . Higher education admission in Hungary by a score-limit algorithm . In Proceedings of the 18th International Conference on Game Theory. Bir\u00f3, P. 2007. Higher education admission in Hungary by a score-limit algorithm. In Proceedings of the 18th International Conference on Game Theory."},{"key":"e_1_2_1_5_1","unstructured":"Boston Public Schools. Student assignment policy. http:\/\/www.bostonpublicschools.org\/assignment\/  Boston Public Schools. Student assignment policy. http:\/\/www.bostonpublicschools.org\/assignment\/"},{"key":"e_1_2_1_6_1","unstructured":"Canadian Resident Matching Service. http:\/\/www.carms.ca.  Canadian Resident Matching Service. http:\/\/www.carms.ca."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.98.3.669"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808776"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90074-5"},{"key":"e_1_2_1_11_1","unstructured":"Gusfield D. and Irving R. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press Cambridge MA.   Gusfield D. and Irving R. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.02.045"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273346"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00179-P"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215048"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9133-x"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.003"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04)","author":"Iwama K.","unstructured":"Iwama , K. , Miyazaki , S. , and Okamoto , K . 2004. A (2 &minus; clog n\/n)-approximation algorithm for the stable marriage problem . In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04) . Springer, Berlin, 349--361. Iwama, K., Miyazaki, S., and Okamoto, K. 2004. A (2 &minus; clog n\/n)-approximation algorithm for the stable marriage problem. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04). Springer, Berlin, 349--361."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_90"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 18th ACM\/SIAM Symposium on Discrete Algorithms (SODA'07)","author":"Iwama K.","unstructured":"Iwama , K. , Miyazaki , S. , and Yamauchi , N . 2007. A 1.875--approximation algorithm for the stable marriage problem . In Proceedings of the 18th ACM\/SIAM Symposium on Discrete Algorithms (SODA'07) . Society for Industrial and Applied Mathematics, Philadelphia, 288--297. Iwama, K., Miyazaki, S., and Yamauchi, N. 2007. A 1.875--approximation algorithm for the stable marriage problem. In Proceedings of the 18th ACM\/SIAM Symposium on Discrete Algorithms (SODA'07). Society for Industrial and Applied Mathematics, Philadelphia, 288--297."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_52"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00206-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_57"},{"key":"e_1_2_1_24_1","unstructured":"National Resident Matching Program. http:\/\/www.nrmp.org.  National Resident Matching Program. http:\/\/www.nrmp.org."},{"key":"e_1_2_1_25_1","first-page":"137","article-title":"Implementation of stable solutions in a restricted matching market","volume":"3","author":"Romero-Medina A.","year":"1998","unstructured":"Romero-Medina , A. 1998 . Implementation of stable solutions in a restricted matching market . Rev. Econ. Des. 3 , 2, 137 -- 147 . Romero-Medina, A. 1998. Implementation of stable solutions in a restricted matching market. Rev. Econ. Des. 3, 2, 137--147.","journal-title":"Rev. Econ. Des."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1086\/261272"},{"key":"e_1_2_1_27_1","unstructured":"Scottish Foundation Allocation Scheme. http:\/\/www.nes.scot.nhs.uk\/sfas.  Scottish Foundation Allocation Scheme. 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\/1498698.1537595","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498698.1537595","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:43Z","timestamp":1750250743000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1537595"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":27,"alternative-id":["10.1145\/1498698.1537595"],"URL":"https:\/\/doi.org\/10.1145\/1498698.1537595","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}