{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:32:31Z","timestamp":1725489151262},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73545-8_53","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T13:44:11Z","timestamp":1187358251000},"page":"548-558","source":"Crossref","is-referenced-by-count":2,"title":["An $\\frac{8}{5}$ -Approximation Algorithm for a Hard Variant of Stable Marriage"],"prefix":"10.1007","author":[{"given":"Robert W.","family":"Irving","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David F.","family":"Manlove","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"53_CR1","unstructured":"(Canadian Resident Matching Service), \n                  \n                    http:\/\/www.carms.ca\/jsp\/main.jsp"},{"key":"53_CR2","doi-asserted-by":"publisher","first-page":"9","DOI":"10.2307\/2312726","volume":"69","author":"D. Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. American Mathematical Monthly\u00a069, 9\u201315 (1962)","journal-title":"American Mathematical Monthly"},{"key":"53_CR3","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 Applied Mathematics\u00a011, 223\u2013232 (1985)","journal-title":"Discrete Applied Mathematics"},{"key":"53_CR4","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. MIT Press, Cambridge (1989)"},{"issue":"1-3","key":"53_CR5","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/S0304-3975(03)00321-9","volume":"306","author":"M. Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson, M., Irving, R.W., Iwama, K., Manlove, D.F., Miyazaki, S., Morita, Y., Scott, S.: Approximability results for stable marriage problems with ties. Theoretical Computer Science\u00a0306(1-3), 431\u2013447 (2003)","journal-title":"Theoretical Computer Science"},{"key":"53_CR6","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":"Algorithms - ESA 2003","author":"M. Halld\u00f3rsson","year":"2003","unstructured":"Halld\u00f3rsson, M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Improved approximation of the stable marriage problem. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 266\u2013277. Springer, Heidelberg (2003)"},{"issue":"3","key":"53_CR7","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/j.tcs.2004.02.045","volume":"325","author":"M.M. Halld\u00f3rsson","year":"2004","unstructured":"Halld\u00f3rsson, M.M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Randomized approximation of the stable marriage problem. Theoretical Computer Science\u00a0325(3), 439\u2013465 (2004)","journal-title":"Theoretical Computer Science"},{"key":"53_CR8","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: A n\n                5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing\u00a02, 225\u2013231 (1973)","journal-title":"SIAM Journal on Computing"},{"key":"53_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/3-540-68530-8_32","volume-title":"Algorithms - ESA \u201998","author":"R.W. Irving","year":"1998","unstructured":"Irving, R.W.: Matching medical students to pairs of hospitals: a new variation on a well-known theme. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 381\u2013392. Springer, Heidelberg (1998)"},{"key":"53_CR10","unstructured":"Irving, R.W., Manlove, D.F.: 8\/5-approximation algorithms for hard variants of the stable marriage and hospitals\/residents problems. Technical Report TR-2007-232, University of Glasgow, Department of Computing Science (February 2007)"},{"key":"53_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1007\/11602613_90","volume-title":"Algorithms and Computation","author":"K. Iwama","year":"2005","unstructured":"Iwama, K., Miyazaki, S., Yamauchi, N.: \n                  \n                    \n                  \n                  $A(2-c{1\\over\\sqrt{n}})$\n                 approximation algorithm for the stable marriage problem. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 902\u2013914. Springer, Heidelberg (2005)"},{"key":"53_CR12","unstructured":"Iwama, K., Miyazaki, S., Yamauchi, N.: A 1.875\u2013approximation algorithm for the stable marriage problem. In: Proceedings of SODA 2007, pp. 288\u2013297 (2007)"},{"issue":"1-2","key":"53_CR13","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","volume":"276","author":"D.F. Manlove","year":"2002","unstructured":"Manlove, D.F., Irving, R.W., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theoretical Computer Science\u00a0276(1-2), 261\u2013279 (2002)","journal-title":"Theoretical Computer Science"},{"key":"53_CR14","unstructured":"(National Resident Matching Program), \n                  \n                    http:\/\/www.nrmp.org\/about_nrmp\/"},{"issue":"6","key":"53_CR15","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1086\/261272","volume":"92","author":"A.E. Roth","year":"1984","unstructured":"Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy\u00a092(6), 991\u20131016 (1984)","journal-title":"Journal of Political Economy"},{"key":"53_CR16","unstructured":"(Scottish Foundation Allocation Scheme), \n                  \n                    http:\/\/www.nes.scot.nhs.uk\/sfas\/"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:18:03Z","timestamp":1619518683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735441","9783540735458"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}