{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:49:08Z","timestamp":1742957348165,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029264"},{"type":"electronic","value":"9783642029271"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_57","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T04:37:10Z","timestamp":1246682230000},"page":"689-700","source":"Crossref","is-referenced-by-count":33,"title":["A 3\/2-Approximation Algorithm for General Stable Marriage"],"prefix":"10.1007","author":[{"given":"Eric","family":"McDermid","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"57_CR1","unstructured":"Bir\u00f3, P.: Student Admissions in Hungary as Gale and Shapley Envisaged. University of Glasgow, Computing Science Department Research Report, TR-2008-291 (2008)"},{"key":"57_CR2","doi-asserted-by":"publisher","first-page":"9","DOI":"10.2307\/2312726","volume":"69","author":"D. Gale","year":"1962","unstructured":"Gale, D., Shapley, L.: College admissions and the stability of marriage. American Mathematical Monthly\u00a069, 9\u201315 (1962)","journal-title":"American Mathematical Monthly"},{"key":"57_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":"57_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":"3","key":"57_CR5","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/1273340.1273346","volume":"3","author":"M. Halld\u00f3rsson","year":"2007","unstructured":"Halld\u00f3rsson, M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Improved approximation results for the stable marriage problem. ACM Trans. Algorithms\u00a03(3), 30 (2007)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"57_CR6","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/j.tcs.2004.02.045","volume":"325","author":"M. Halld\u00f3rsson","year":"2004","unstructured":"Halld\u00f3rsson, 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"},{"issue":"3","key":"57_CR7","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1137\/0215048","volume":"15","author":"R.W. Irving","year":"1986","unstructured":"Irving, R.W., Leather, P.: The complexity of counting stable marriages. SIAM Journal on Computing\u00a015(3), 655\u2013667 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"57_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10878-007-9133-x","volume":"16","author":"R.W. Irving","year":"2008","unstructured":"Irving, R.W., Manlove, D.F.: Approximation algorithms for hard variants of the stable marriage and hospitals\/residents problems. Journal of Combinatorial Optimization\u00a016, 279\u2013292 (2008)","journal-title":"Journal of Combinatorial Optimization"},{"key":"57_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-540-27810-8_30","volume-title":"Algorithm Theory - SWAT 2004","author":"K. Iwama","year":"2004","unstructured":"Iwama, K., Miyazaki, S., Okamoto, K.: A \n                    \n                      \n                    \n                    $\\left(2-c\\frac{\\log n}{n}\\right)$\n                  -approximation algorithm for the stable marriage problem. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 349\u2013361. Springer, Heidelberg (2004)"},{"issue":"3","key":"57_CR10","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/s00453-007-9101-y","volume":"51","author":"K. Iwama","year":"2008","unstructured":"Iwama, K., Miyazaki, S., Yamauchi, N.: A \n                    \n                      \n                    \n                    $(2-c(1\/\\sqrt(N)))$\n                  -Approximation Algorithm for the Stable Marriage Problem. Algorithmica\u00a051(3), 342\u2013356 (2008)","journal-title":"Algorithmica"},{"key":"57_CR11","unstructured":"Iwama, K., Miyazaki, S., Yamauchi, N.: A 1.875\u2013approximation algorithm for the stable marriage problem. In: 18th ACM\/SIAM Symposium on Discrete Algorithms, pp. 288\u2013297 (2007)"},{"key":"57_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/978-3-540-87744-8_52","volume-title":"Algorithms - ESA 2008","author":"Z. Kir\u00e1ly","year":"2008","unstructured":"Kir\u00e1ly, Z.: Better and simpler approximation algorithms for the stable marriage problem. In: Halperin, D., Mehlhorn, K. (eds.) Esa 2008. LNCS, vol.\u00a05193, pp. 623\u2013634. Springer, Heidelberg (2008)"},{"key":"57_CR13","unstructured":"Knuth, D.E.: Mariages Stables. Les Presses de L\u2019Universit\u00e9 de Montr\u00e9al (1976)"},{"key":"57_CR14","series-title":"Annals of Discrete Mathematics","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. Annals of Discrete Mathematics, vol.\u00a029. North-Holland, Amsterdam (1986)"},{"issue":"1-2","key":"57_CR15","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":"57_CR16","unstructured":"Canadian Resident Matching Service, \n                    \n                      http:\/\/www.carms.ca\/jsp\/main.jsp"},{"key":"57_CR17","unstructured":"National Resident Matching Program, \n                    \n                      http:\/\/www.nrmp.org\/about_nrmp\/how.html"},{"key":"57_CR18","unstructured":"Scottish Foundation Allocation Scheme, \n                    \n                      http:\/\/www.nes.scot.nhs.uk\/sfas\/"},{"key":"57_CR19","unstructured":"Yanagisawa, H.: Approximation algorithms for stable marriage problems, PhD thesis, Kyoto University, Graduate School of Informatics (2007)"},{"key":"57_CR20","unstructured":"Yanagisawa, H.: Personal communication (2008)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T20:39:07Z","timestamp":1552077547000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}