{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:08Z","timestamp":1759639088862},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434009"},{"type":"electronic","value":"9783540459958"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45995-2_48","type":"book-chapter","created":{"date-parts":[[2007,5,30]],"date-time":"2007-05-30T02:33:34Z","timestamp":1180492414000},"page":"554-568","source":"Crossref","is-referenced-by-count":7,"title":["Inapproximability Results on Stable Marriage Problems"],"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":"Yasufumi","family":"Morita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,14]]},"reference":[{"key":"48_CR1","unstructured":"S. Arora and C. Lund, \u201cHardness of Approximations,\u201d Chapter in the bookApproximation Algorithms for NP-hard problems, D. Hochbaum editor, PWS Publishing, 1996."},{"key":"48_CR2","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","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":"48_CR3","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":"48_CR4","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0216010","volume":"16","author":"D. Gusfield","year":"1987","unstructured":"D. Gusfield, \u201cThree fast algorithms for four problems in stable marriage,\u201d SIAM Journal on Computing, Vol. 16, pp. 111\u2013128, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"48_CR5","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":"48_CR6","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, \u201cSome optimal inapproximability results,\u201d Proc. STOC 97, pp. 1\u201311, 1997.","DOI":"10.1145\/258533.258536"},{"key":"48_CR7","first-page":"532","volume":"34","author":"R. W. Irving","year":"1987","unstructured":"R. W. Irving, P. Leather and D. Gusfield, \u201cAn efficient algorithm for the \u201coptimal\u201d stable marriage,\u201d Journal of the A.C.M., Vol. 34, pp. 532\u2013543, 1987.","journal-title":"Journal of the A.C.M."},{"key":"48_CR8","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":"48_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/3-540-44985-X_24","volume-title":"The hospital\/residents problem with ties","author":"R. W. Irving","year":"2000","unstructured":"R. W. Irving, D. F. Manlove and S. Scott, \u201cThe hospital\/residents problem with ties,\u201d Proc. SWAT 2000, LNCS 1851, pp. 259\u2013271, 2000."},{"key":"48_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/3-540-48523-6_41","volume-title":"Stable marriage with incomplete lists and ties","author":"K. Iwama","year":"1999","unstructured":"K. Iwama, D. Manlove, S. Miyazaki, and Y. Morita, \u201cStable marriage with incomplete lists and ties,\u201d Proc. ICALP\u201999, LNCS 1644, pp. 443\u2013452, 1999."},{"key":"48_CR11","unstructured":"D. Manlove, R. W. Irving, K. Iwama, S. Miyazaki, Y. Morita, \u201cHard variants of stable marriage,\u201d Technical Report TR-1999-43, Computing Science Department of Glasgow University, September 1999 (to appear in Theoretical Computer Science)."},{"key":"48_CR12","doi-asserted-by":"crossref","unstructured":"E. Ronn,\u201cNP-complete stable matching problems,\u201d J. Algorithms, Vol.11, pp.285\u2013304, 1990.","DOI":"10.1016\/0196-6774(90)90007-2"},{"key":"48_CR13","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer, \u201cThe complexity of satis.ability problems,\u201d Proc. STOC 78, pp.216\u2013226, 1978.","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","LATIN 2002: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45995-2_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T00:38:10Z","timestamp":1550363890000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45995-2_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434009","9783540459958"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-45995-2_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2002]]}}}