{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T07:48:50Z","timestamp":1781941730041,"version":"3.54.5"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,12,22]],"date-time":"2007-12-22T00:00:00Z","timestamp":1198281600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s10878-007-9133-x","type":"journal-article","created":{"date-parts":[[2007,12,21]],"date-time":"2007-12-21T15:38:05Z","timestamp":1198251485000},"page":"279-292","source":"Crossref","is-referenced-by-count":28,"title":["Approximation algorithms for hard variants of the stable marriage and hospitals\/residents problems"],"prefix":"10.1007","volume":"16","author":[{"given":"Robert W.","family":"Irving","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David F.","family":"Manlove","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,12,22]]},"reference":[{"key":"9133_CR1","unstructured":"Canadian Resident Matching Service website http:\/\/www.carms.ca\/"},{"issue":"1","key":"9133_CR2","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1145\/1077464.1077474","volume":"1","author":"K Cechl\u00e1rov\u00e1","year":"2005","unstructured":"Cechl\u00e1rov\u00e1 K, Fleiner T (2005) On a generalization of the stable roommates problem. ACM Trans Algorithms 1(1):143\u2013156","journal-title":"ACM Trans Algorithms"},{"key":"9133_CR3","doi-asserted-by":"crossref","unstructured":"Gabow HN (1983) An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of STOC \u201983: the 15th annual ACM symposium on theory of computing. ACM, pp\u00a0448\u2013456","DOI":"10.1145\/800061.808776"},{"key":"9133_CR4","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Mon 69:9\u201315","journal-title":"Am Math Mon"},{"key":"9133_CR5","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(85)90074-5","volume":"11","author":"D Gale","year":"1985","unstructured":"Gale D, Sotomayor M (1985) Some remarks on the stable matching problem. Discrete Appl Math 11:223\u2013232","journal-title":"Discrete Appl Math"},{"key":"9133_CR6","volume-title":"The stable marriage problem: structure and algorithms","author":"D Gusfield","year":"1989","unstructured":"Gusfield D, Irving RW (1989) The stable marriage problem: structure and algorithms. MIT Press, Cambridge"},{"issue":"1\u20133","key":"9133_CR7","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/S0304-3975(03)00321-9","volume":"306","author":"M Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson M, Irving RW, Iwama K, Manlove DF, Miyazaki S, Morita Y, Scott S (2003a) Approximability results for stable marriage problems with ties. Theor Comput Sci 306(1\u20133):431\u2013447","journal-title":"Theor Comput Sci"},{"key":"9133_CR8","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/978-3-540-39658-1_26","volume-title":"Proceedings of ESA 2003: the eleventh European symposium on algorithms","author":"M Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson M, Iwama K, Miyazaki S, Yanagisawa H (2003b) Improved approximation of the stable marriage problem. In: Proceedings of ESA 2003: the eleventh European symposium on algorithms. Lecture notes in computer science, vol\u00a02832. Springer, Berlin, pp\u00a0266\u2013277"},{"issue":"3","key":"9133_CR9","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/j.tcs.2004.02.045","volume":"325","author":"MM Halld\u00f3rsson","year":"2004","unstructured":"Halld\u00f3rsson MM, Iwama K, Miyazaki S, Yanagisawa H (2004) Randomized approximation of the stable marriage problem. Theor Comput Sci 325(3):439\u2013465","journal-title":"Theor Comput Sci"},{"key":"9133_CR10","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft JE, Karp RM (1973) A n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J\u00a0Comput 2:225\u2013231","journal-title":"SIAM J\u00a0Comput"},{"key":"9133_CR11","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","volume":"48","author":"RW Irving","year":"1994","unstructured":"Irving RW (1994) Stable marriage and indifference. Discrete Appl Math 48:261\u2013272","journal-title":"Discrete Appl Math"},{"key":"9133_CR12","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/3-540-68530-8_32","volume-title":"Proceedings of ESA \u201998: the sixth European symposium on algorithms","author":"RW Irving","year":"1998","unstructured":"Irving RW (1998) Matching medical students to pairs of hospitals: a new variation on a well-known theme. In: Proceedings of ESA \u201998: the sixth European symposium on algorithms. Lecture notes in computer science, vol\u00a01461. Springer, Berlin, pp\u00a0381\u2013392"},{"issue":"3","key":"9133_CR13","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1137\/0215048","volume":"15","author":"RW Irving","year":"1986","unstructured":"Irving RW, Leather P (1986) The complexity of counting stable marriages. SIAM J\u00a0Comput 15(3):655\u2013667","journal-title":"SIAM J\u00a0Comput"},{"key":"9133_CR14","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"548","DOI":"10.1007\/978-3-540-73545-8_53","volume-title":"Proceedings of COCOON 2007, 13th annual international computing and combinatorics conference, Banff, Canada","author":"RW Irving","year":"2007","unstructured":"Irving RW, Manlove DF (2007) An 8\/5 approximation algorithm for a hard variant of stable marriage. In: Proceedings of COCOON 2007, 13th annual international computing and combinatorics conference, Banff, Canada. Lecture notes in computer science, vol\u00a04598. Springer, Berlin, pp\u00a0548\u2013558"},{"key":"9133_CR15","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/3-540-44985-X_24","volume-title":"Proceedings of SWAT 2000: the 7th Scandinavian workshop on algorithm theory","author":"RW Irving","year":"2000","unstructured":"Irving RW, Manlove DF, Scott S (2000) The hospitals\/residents problem with ties. In: Proceedings of SWAT 2000: the 7th Scandinavian workshop on algorithm theory. Lecture notes in computer science, vol\u00a01851. Springer, Berlin, pp\u00a0259\u2013271"},{"key":"9133_CR16","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/3-540-36494-3_39","volume-title":"Proceedings of STACS 2003: the 20th annual symposium on theoretical aspects of computer science","author":"RW Irving","year":"2003","unstructured":"Irving RW, Manlove DF, Scott S (2003) Strong stability in the hospitals\/residents problem. In: Proceedings of STACS 2003: the 20th annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol\u00a02607. Springer, Berlin, pp\u00a0439\u2013450"},{"key":"9133_CR17","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/978-3-540-27810-8_30","volume-title":"Proceedings of SWAT 2004: the 9th Scandinavian workshop on algorithm theory","author":"K Iwama","year":"2004","unstructured":"Iwama K, Miyazaki S, Okamoto K (2004) A $(2-c\\frac{\\log n}{n})$ -approximation algorithm for the stable marriage problem. In: Proceedings of SWAT 2004: the 9th Scandinavian workshop on algorithm theory. Lecture notes in computer science, vol\u00a03111. Springer, Berlin, pp\u00a0349\u2013361"},{"key":"9133_CR18","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1007\/11602613_90","volume-title":"Proceedings of ISAAC 2005: the sixteenth international symposium on algorithms and computation","author":"K Iwama","year":"2005","unstructured":"Iwama K, Miyazaki S, Yamauchi N (2005) A $(2-c\\frac{1}{\\sqrt{n}})$ -approximation algorithm for the stable marriage problem. In: Proceedings of ISAAC 2005: the sixteenth international symposium on algorithms and computation. Lecture notes in computer science, vol\u00a03827. Springer, Berlin, pp\u00a0902\u2013914"},{"key":"9133_CR19","unstructured":"Iwama K, Miyazaki S, Yamauchi N (2007) A 1.875-approximation algorithm for the stable marriage problem. In: Proceedings of SODA 2007: the eighteenth ACM\/SIAM symposium on discrete algorithms, pp\u00a0288\u2013297"},{"issue":"1\u20132","key":"9133_CR20","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","volume":"276","author":"DF Manlove","year":"2002","unstructured":"Manlove DF, Irving RW, Iwama K, Miyazaki S, Morita Y (2002) Hard variants of stable marriage. Theor Comput Sci 276(1\u20132):261\u2013279","journal-title":"Theor Comput Sci"},{"key":"9133_CR21","unstructured":"National Resident Matching Program website http:\/\/www.nrmp.org\/about_nrmp\/how.html"},{"issue":"6","key":"9133_CR22","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1086\/261272","volume":"92","author":"AE Roth","year":"1984","unstructured":"Roth AE (1984) The evolution of the labor market for medical interns and residents: a case study in game theory. J\u00a0Political Econ 92(6):991\u20131016","journal-title":"J\u00a0Political Econ"},{"key":"9133_CR23","series-title":"Econometric society monographs","doi-asserted-by":"crossref","DOI":"10.1017\/CCOL052139015X","volume-title":"Two-sided matching: a study in game-theoretic modeling and analysis","author":"AE Roth","year":"1990","unstructured":"Roth AE, Sotomayor MAO (1990) Two-sided matching: a study in game-theoretic modeling and analysis. Econometric society monographs, vol\u00a018. Cambridge University Press, Cambridge"},{"key":"9133_CR24","unstructured":"Scottish Foundation Allocation Scheme website http:\/\/www.nes.scot.nhs.uk\/sfas\/"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9133-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-007-9133-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9133-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:12Z","timestamp":1559276292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-007-9133-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,22]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9133"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9133-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,22]]}}}