{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T02:40:48Z","timestamp":1773801648449,"version":"3.50.1"},"reference-count":22,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3643,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,9]]},"DOI":"10.1016\/s0304-3975(03)00321-9","type":"journal-article","created":{"date-parts":[[2003,6,30]],"date-time":"2003-06-30T14:16:39Z","timestamp":1056982599000},"page":"431-447","source":"Crossref","is-referenced-by-count":50,"title":["Approximability results for stable marriage problems with ties"],"prefix":"10.1016","volume":"306","author":[{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[]},{"given":"Robert W.","family":"Irving","sequence":"additional","affiliation":[]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[]},{"given":"David F.","family":"Manlove","sequence":"additional","affiliation":[]},{"given":"Shuichi","family":"Miyazaki","sequence":"additional","affiliation":[]},{"given":"Yasufumi","family":"Morita","sequence":"additional","affiliation":[]},{"given":"Sandy","family":"Scott","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(03)00321-9_BIB1","unstructured":"Canadian Resident Matching Service, How the matching algorithm works. Web document available at http:\/\/www.carms.ca\/matching\/algorith.htm."},{"key":"10.1016\/S0304-3975(03)00321-9_BIB2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0022-0000(92)90048-N","article-title":"A new fixed point approach for stable networks and stable marriages","volume":"45","author":"Feder","year":"1992","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(03)00321-9_BIB3","doi-asserted-by":"crossref","first-page":"9","DOI":"10.2307\/2312726","article-title":"College admissions and the stability of marriage","volume":"69","author":"Gale","year":"1962","journal-title":"Amer. Math. Monthly"},{"key":"10.1016\/S0304-3975(03)00321-9_BIB4","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(85)90074-5","article-title":"Some remarks on the stable matching problem","volume":"11","author":"Gale","year":"1985","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(03)00321-9_BIB5","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"issue":"1","key":"10.1016\/S0304-3975(03)00321-9_BIB6","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0216010","article-title":"Three fast algorithms for four problems in stable marriage","volume":"16","author":"Gusfield","year":"1987","journal-title":"SIAM J. Comput"},{"key":"10.1016\/S0304-3975(03)00321-9_BIB7","series-title":"The Stable Marriage Problem: Structure and Algorithms","author":"Gusfield","year":"1989"},{"key":"10.1016\/S0304-3975(03)00321-9_BIB8","doi-asserted-by":"crossref","unstructured":"M. Halld\u00f3rsson, K. Iwama, S. Miyazaki, Y. Morita, Inapproximability results on stable marriage problems, in: Proc. LATIN 2002: the Latin-American Theoretical INformatics symposium, Lecture Notes in Computer Science, Vol. 2286, Springer, Berlin, 2002, pp. 554\u2013568.","DOI":"10.1007\/3-540-45995-2_48"},{"key":"10.1016\/S0304-3975(03)00321-9_BIB9","doi-asserted-by":"crossref","unstructured":"M. Halld\u00f3rsson, K. Yoshihara, Greedy approximations of independent sets in low degree graphs, in: Proc. ISAAC \u201995: the 6th Internat. Symp. on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 1004, Springer, Berlin, 1995, pp. 152\u2013161.","DOI":"10.1007\/BFb0015418"},{"key":"10.1016\/S0304-3975(03)00321-9_BIB10","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1137\/0406030","article-title":"Minimum edge dominating sets","volume":"6","author":"Horton","year":"1993","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0304-3975(03)00321-9_BIB11","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","article-title":"Stable marriage and indifference","volume":"48","author":"Irving","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(03)00321-9_BIB12","doi-asserted-by":"crossref","unstructured":"R.W. Irving, Matching medical students to pairs of hospitals: a new variation on a well-known theme, in: Proc. ESA \u201998: 6th European Symp. on Algorithms, Lecture Notes in Computer Science, Vol. 1461, Springer, Berlin, 1998, pp. 381\u2013392.","DOI":"10.1007\/3-540-68530-8_32"},{"issue":"3","key":"10.1016\/S0304-3975(03)00321-9_BIB13","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1145\/28869.28871","article-title":"An efficient algorithm for the \u201coptimal\u201d stable marriage","volume":"34","author":"Irving","year":"1987","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0304-3975(03)00321-9_BIB14","doi-asserted-by":"crossref","unstructured":"R.W. Irving, D.F. Manlove, S. Scott, The Hospitals\/Residents problem with Ties, in: Proc. SWAT 2000: 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 1851, Springer, Berlin, 2000, pp. 259\u2013271.","DOI":"10.1007\/3-540-44985-X_24"},{"key":"10.1016\/S0304-3975(03)00321-9_BIB15","doi-asserted-by":"crossref","unstructured":"K. Iwama, D. Manlove, S. Miyazaki, Y. Morita, Stable marriage with incomplete lists and ties, in: Proc. ICALP \u201999: 26th Internat. Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 1644, Springer, Berlin, 1999, pp. 443\u2013452.","DOI":"10.1007\/3-540-48523-6_41"},{"key":"10.1016\/S0304-3975(03)00321-9_BIB16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF03167200","article-title":"Complexity of the sex-equal stable marriage problem","volume":"10","author":"Kato","year":"1993","journal-title":"Japan J. Ind. Appl. Math."},{"key":"10.1016\/S0304-3975(03)00321-9_BIB17","doi-asserted-by":"crossref","unstructured":"D.E. Knuth, Stable Marriage and its Relation to Other Combinatorial Problems, in: CRM Proceedings and Lecture Notes, Vol. 10, American Mathematical Society, Providence, RI, 1997 (English translation of Marriages Stables, Les Presses de L'Universit\u00e9 de Montr\u00e9al, 1976).","DOI":"10.1090\/crmp\/010"},{"issue":"1\u20132","key":"10.1016\/S0304-3975(03)00321-9_BIB18","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","article-title":"Hard variants of stable marriage","volume":"276","author":"Manlove","year":"2002","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(03)00321-9_BIB19","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0196-6774(90)90007-2","article-title":"NP-complete stable matching problems","volume":"11","author":"Ronn","year":"1990","journal-title":"J. Algorithms"},{"issue":"6","key":"10.1016\/S0304-3975(03)00321-9_BIB20","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1086\/261272","article-title":"The evolution of the labor market for medical interns and residents","volume":"92","author":"Roth","year":"1984","journal-title":"J. Polit. Econ."},{"key":"10.1016\/S0304-3975(03)00321-9_BIB21","article-title":"Two-sided matching: a study in game-theoretic modeling and analysis","volume":"Vol. 18","author":"Roth","year":"1990"},{"key":"10.1016\/S0304-3975(03)00321-9_BIB22","series-title":"Approximation Algorithms","author":"Vazirani","year":"2001"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397503003219?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397503003219?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T08:38:25Z","timestamp":1585039105000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397503003219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,9]]},"references-count":22,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2003,9]]}},"alternative-id":["S0304397503003219"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(03)00321-9","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,9]]}}}