{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T05:11:49Z","timestamp":1759813909718},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,10,18]],"date-time":"2012-10-18T00:00:00Z","timestamp":1350518400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s00453-012-9699-2","type":"journal-article","created":{"date-parts":[[2012,10,17]],"date-time":"2012-10-17T22:30:26Z","timestamp":1350513026000},"page":"758-775","source":"Crossref","is-referenced-by-count":22,"title":["A 25\/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties"],"prefix":"10.1007","volume":"68","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[]},{"given":"Shuichi","family":"Miyazaki","sequence":"additional","affiliation":[]},{"given":"Hiroki","family":"Yanagisawa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,10,18]]},"reference":[{"issue":"2","key":"9699_CR1","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1257\/000282805774669637","volume":"95","author":"A. Abdulkadiro\u01e7lu","year":"2005","unstructured":"Abdulkadiro\u01e7lu, A., Pathak, P.A., Roth, A.E., S\u00f6nmez, T.: The Boston public school match. Am. Econ. Rev. 95(2), 368\u2013371 (2005)","journal-title":"Am. Econ. Rev."},{"key":"9699_CR2","doi-asserted-by":"crossref","unstructured":"Abdulkadiro\u01e7lu, A., Pathak, P.A., Roth, A.E., S\u00f6nmez, T.: Changing the Boston school choice mechanism: strategy-proofness as equal access. Manuscript (2006)","DOI":"10.3386\/w11965"},{"key":"9699_CR3","doi-asserted-by":"crossref","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. Am. Math. Mon. 69, 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"9699_CR4","doi-asserted-by":"crossref","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 Appl. Math. 11, 223\u2013232 (1985)","journal-title":"Discrete Appl. Math."},{"key":"9699_CR5","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, Boston (1989)"},{"issue":"3","key":"9699_CR6","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 325(3), 439\u2013465 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9699_CR7","doi-asserted-by":"crossref","DOI":"10.1145\/1273340.1273346","volume":"3","author":"M.M. Halld\u00f3rsson","year":"2007","unstructured":"Halld\u00f3rsson, M.M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Improved approximation results for the stable marriage problem. ACM Trans. Algorithms 3(3), 30 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9699_CR8","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","volume":"48","author":"R.W. Irving","year":"1994","unstructured":"Irving, R.W.: Stable marriage and indifference. Discrete Appl. Math. 48, 261\u2013272 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9699_CR9","doi-asserted-by":"crossref","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. J. Comb. Optim. 16(3), 279\u2013292 (2008)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"9699_CR10","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.jda.2008.09.003","volume":"7","author":"R.W. Irving","year":"2009","unstructured":"Irving, R.W., Manlove, D.F., O\u2019Malley, G.: Stable marriage with ties and bounded length preference lists. J. Discrete Algorithms 7(2), 213\u2013219 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"9699_CR11","series-title":"LNCS","first-page":"443","volume-title":"Proc. ICALP","author":"K. Iwama","year":"1999","unstructured":"Iwama, K., Manlove, D.F., Miyazaki, S., Morita, Y.: Stable marriage with incomplete lists and ties. In: Proc. ICALP. LNCS, vol. 1644, pp. 443\u2013452 (1999)"},{"key":"9699_CR12","doi-asserted-by":"crossref","first-page":"2380","DOI":"10.1093\/ietisy\/e89-d.8.2380","volume":"89-D(8)","author":"K. Iwama","year":"2006","unstructured":"Iwama, K., Miyazaki, S., Okamoto, K.: \u201cA (2\u2212clogN\/N)-approximation algorithm for the stable marriage problem. IEICE Transactions 89-D(8), 2380\u20132387 (2006)","journal-title":"IEICE Transactions"},{"issue":"3","key":"9699_CR13","doi-asserted-by":"crossref","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 ( $2-c\\frac{1}{\\sqrt{N}}$ )-approximation algorithm for the stable marriage problem. Algorithmica 51(3), 342\u2013356 (2008)","journal-title":"Algorithmica"},{"key":"9699_CR14","first-page":"288","volume-title":"Proc. SODA","author":"K. Iwama","year":"2007","unstructured":"Iwama, K., Miyazaki, S., Yamauchi, N.: A 1.875-approximation algorithm for the stable marriage problem. In: Proc. SODA, pp. 288\u2013297 (2007)"},{"issue":"1","key":"9699_CR15","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00453-009-9371-7","volume":"60","author":"Z. Kir\u00e1ly","year":"2011","unstructured":"Kir\u00e1ly, Z.: Better and simpler approximation algorithms for the stable marriage problem. Algorithmica 60(1), 3\u201320 (2011)","journal-title":"Algorithmica"},{"issue":"3","key":"9699_CR16","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S. Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2212\u03f5. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"9699_CR17","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 276(1\u20132), 261\u2013279 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9699_CR18","series-title":"LNCS","first-page":"689","volume-title":"Proc. ICALP","author":"E.J. McDermid","year":"2009","unstructured":"McDermid, E.J.: A 3\/2-approximation algorithm for general stable marriage. In: Proc. ICALP. LNCS, vol. 5555, pp. 689\u2013700 (2009)"},{"issue":"4","key":"9699_CR19","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1257\/aer.89.4.748","volume":"89","author":"A.E. Roth","year":"1999","unstructured":"Roth, A.E., Peranson, E.: The redesign of the matching market for American physicians: some engineering aspects of economic design. Am. Econ. Rev. 89(4), 748\u2013780 (1999)","journal-title":"Am. Econ. Rev."},{"issue":"4","key":"9699_CR20","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1287\/moor.18.4.803","volume":"18","author":"A.E. Roth","year":"1993","unstructured":"Roth, A.E., Rothblum, U.G., Vate, J.H.V.: Stable matchings, optimal assignments, and linear programming. Math. Oper. Res. 18(4), 803\u2013828 (1993)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"9699_CR21","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1287\/moor.23.4.874","volume":"23","author":"C.-P. Teo","year":"1998","unstructured":"Teo, C.-P., Sethuraman, J.: The geometry of fractional stable matchings and its applications. Math. Oper. Res. 23(4), 874\u2013891 (1998)","journal-title":"Math. Oper. Res."},{"key":"9699_CR22","series-title":"LNCS","first-page":"429","volume-title":"Proc. IPCO","author":"C.-P. Teo","year":"1999","unstructured":"Teo, C.-P., Sethuraman, J., Tan, W.P.: Gale-Shapley stable marriage problem revisited: strategic issues and applications. In: Proc. IPCO. LNCS, vol. 1610, pp. 429\u2013438 (1999)"},{"key":"9699_CR23","unstructured":"Yanagisawa, H.: Approximation algorithms for stable marriage problems. Ph. D. Thesis, Kyoto University (2007)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9699-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9699-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9699-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:10Z","timestamp":1559137510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9699-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,18]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["9699"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9699-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,18]]}}}