{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:47:48Z","timestamp":1725493668622},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405344"},{"type":"electronic","value":"9783540450719"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45071-8_35","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T08:04:43Z","timestamp":1193472283000},"page":"339-350","source":"Crossref","is-referenced-by-count":3,"title":["Randomized Approximation of the Stable Marriage Problem"],"prefix":"10.1007","author":[{"given":"Magn\u00fas","family":"Halld\u00f3rsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuichi","family":"Miyazaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroki","family":"Yanagisawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"key":"35_CR1","doi-asserted-by":"publisher","first-page":"9","DOI":"10.2307\/2312726","volume":"69","author":"D. Gale","year":"1962","unstructured":"D. Gale and L. S. Shapley, \u201cCollege admissions and the stability of marriage,\u201d Amer. Math. Monthly, Vol.69, pp.9\u201315, 1962.","journal-title":"Amer. Math. Monthly"},{"key":"35_CR2","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0166-218X(85)90074-5","volume":"11","author":"D. Gale","year":"1985","unstructured":"D. Gale and M. Sotomayor, \u201cSome remarks on the stable matching problem,\u201d Discrete Applied Mathematics, Vol.11, pp.223\u2013232, 1985.","journal-title":"Discrete Applied Mathematics"},{"key":"35_CR3","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"D. Gusfield","year":"1989","unstructured":"D. Gusfield and R. W. Irving, \u201cThe Stable Marriage Problem: Structure and Algorithms,\u201d MIT Press, Boston, MA, 1989."},{"key":"35_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1007\/3-540-45995-2_48","volume-title":"Proc. LATIN2002","author":"M. Halld\u00f3rsson","year":"2002","unstructured":"M. Halld\u00f3rsson, K. Iwama, S. Miyazaki and Y. Morita, \u201cInapproximability Results on Stable Marriage Problems,\u201d Proc. LATIN2002, LNCS 2286, pp.554\u2013568, 2002."},{"key":"35_CR5","unstructured":"E. Halperin, \u201cImproved approximation algorithms for the vertex cover problem in graphs and hypergraphs,\u201d Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 329\u2013337, 2000."},{"key":"35_CR6","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","volume":"48","author":"R. W. Irving","year":"1994","unstructured":"R. W. Irving, \u201cStable marriage and indifference,\u201d Discrete Applied Mathematics, Vol.48, pp.261\u2013272, 1994.","journal-title":"Discrete Applied Mathematics"},{"key":"35_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/3-540-48523-6_41","volume-title":"Proc. ICALP\u201999","author":"K. Iwama","year":"1999","unstructured":"K. Iwama, D. Manlove, S. Miyazaki, and Y. Morita, \u201cStable marriage with incomplete lists and ties,\u201d In Proc. ICALP\u201999, LNCS 1644, pp. 443\u2013452, 1999."},{"issue":"1\u20132","key":"35_CR8","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","volume":"276","author":"D. Manlove","year":"2002","unstructured":"D. Manlove, R. W. Irving, K. Iwama, S. Miyazaki, Y. Morita, \u201cHard variants of stable marriage,\u201d Theoretical Computer Science, Vol. 276, Issue 1\u20132, pp. 261\u2013279, 2002.","journal-title":"Theoretical Computer Science"},{"key":"35_CR9","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"B. Monien and E. Speckenmeyer, \u201cRamsey numbers and an approximation algorithm for the vertex cover problem,\u201d Acta Inf., Vol. 22, pp. 115\u2013123, 1985.","journal-title":"Acta Inf."},{"key":"35_CR10","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M. Yannakakis","year":"1980","unstructured":"M. Yannakakis and F. Gavril,\u201cEdge dominating sets in graphs,\u201d SIAM J. Appl. Math., Vol. 38, pp. 364\u2013372, 1980.","journal-title":"SIAM J. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45071-8_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T16:27:01Z","timestamp":1551025621000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45071-8_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405344","9783540450719"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-45071-8_35","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}