{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T11:10:22Z","timestamp":1782817822929,"version":"3.54.5"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T00:00:00Z","timestamp":1435017600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s10107-015-0923-0","type":"journal-article","created":{"date-parts":[[2015,6,22]],"date-time":"2015-06-22T04:23:53Z","timestamp":1434947033000},"page":"353-380","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Improved approximation algorithms for two variants of the stable marriage problem with ties"],"prefix":"10.1007","volume":"154","author":[{"given":"Chien-Chung","family":"Huang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Telikepalli","family":"Kavitha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,23]]},"reference":[{"key":"923_CR1","doi-asserted-by":"crossref","unstructured":"Askalidis, G., Immorlica, N., Kwanashie, A., Manlove, D., Pountourakis E.: Socially stable matchings in the hospitals\/residents problem. In: Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 8037, pp. 85\u201396. Springer, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40104-6_8"},{"key":"923_CR2","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":"923_CR3","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., Sotomayer, M.: Some remarks on the stable marriage problem. Discrete Appl. Math. 11, 223\u2013232 (1985)","journal-title":"Discrete Appl. Math."},{"key":"923_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, Boston, MA (1989)"},{"issue":"3","key":"923_CR5","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/1273340.1273346","volume":"3","author":"MM 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"},{"issue":"3","key":"923_CR6","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/j.tcs.2004.02.045","volume":"325","author":"MM 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."},{"key":"923_CR7","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","volume":"48","author":"RW 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":"923_CR8","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s10878-007-9133-x","volume":"16","author":"RW 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."},{"key":"923_CR9","doi-asserted-by":"crossref","unstructured":"Iwama, K., Manlove, D.F., Miyazaki, S., Morita, Y.: Stable marriage with incomplete lists and ties. In: 36th ICALP, pp. 443\u2013452 (1999)","DOI":"10.1007\/3-540-48523-6_41"},{"key":"923_CR10","unstructured":"Iwama, K., Miyazaki, S., Yamauchi, N.: A 1.875\u2014approximation algorithm for the stable marriage problem. In: 18th SODA, pp. 288\u2013297 (2007)"},{"issue":"3","key":"923_CR11","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1007\/s00453-012-9699-2","volume":"68","author":"K Iwama","year":"2014","unstructured":"Iwama, K., Miyazaki, S., Yanagisawa, H.: A 25\/17\u2014approximation algorithm for the stable marriage problem with one-sided ties. Algorithmica 68(3), 758\u2013775 (2014)","journal-title":"Algorithmica"},{"issue":"1","key":"923_CR12","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":"923_CR13","doi-asserted-by":"crossref","first-page":"471","DOI":"10.3390\/a6030471","volume":"6","author":"Z Kir\u00e1ly","year":"2013","unstructured":"Kir\u00e1ly, Z.: Linear time local approximation algorithm for maximum stable marriage. Algorithms 6(3), 471\u2013484 (2013)","journal-title":"Algorithms"},{"key":"923_CR14","unstructured":"Knuth, D.: Mariages stables et leurs relations avec d\u2019autre probl\u00e8mes. Les Presses de l\u2019universit\u00e9 de Montr\u00e9al (1976)"},{"key":"923_CR15","doi-asserted-by":"crossref","DOI":"10.1142\/8591","volume-title":"Algorithmics of Matching Under Preferences","author":"D Manlove","year":"2013","unstructured":"Manlove, D.: Algorithmics of Matching Under Preferences. World Scientific Publishing Company, Singapore (2013)"},{"issue":"1\u20132","key":"923_CR16","first-page":"179","volume":"276","author":"DF 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), 179\u2013261 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"923_CR17","doi-asserted-by":"crossref","unstructured":"McDermid, E. J.: A 3\/2 approximation algorithm for general stable marriage. In: 36th ICALP, pp. 689\u2013700 (2009)","DOI":"10.1007\/978-3-642-02927-1_57"},{"key":"923_CR18","doi-asserted-by":"crossref","unstructured":"Paluch, K.: Faster and simpler approximation of stable matchings. In: 9th WAOA, pp. 176\u2013187 (2011)","DOI":"10.1007\/978-3-642-29116-6_15"},{"key":"923_CR19","unstructured":"Radnai, A.: Approximation algorithms for the stable matching problem. Master Thesis, Department of computer science, E\u00f6tv\u00f6s Lor\u00e1nd University (2014)"},{"key":"923_CR20","volume-title":"Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis","author":"A Roth","year":"1992","unstructured":"Roth, A., Sotomayor, M.: Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press, Cambridge (1992)"},{"key":"923_CR21","doi-asserted-by":"crossref","unstructured":"Teo, C.-P., Sethuraman, J., Tan, W.P.: Gale-Shapley stable marriage problem revisited: strategic issues and applications. In: 7th IPCO, pp. 429\u2013438 (1999)","DOI":"10.1007\/3-540-48777-8_32"},{"key":"923_CR22","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0167-6377(89)90041-2","volume":"8","author":"JV Vate","year":"1989","unstructured":"Vate, J.V.: Linear programming brings marital bliss. Oper. Res. Lett. 8, 147\u2013153 (1989)","journal-title":"Oper. Res. Lett."},{"key":"923_CR23","unstructured":"Yanagisawa, H.: Approximation algorithms for stable marriage problems. Ph.D. Thesis, Kyoto University (2007)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0923-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0923-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0923-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,27]],"date-time":"2019-08-27T13:31:08Z","timestamp":1566912668000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0923-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,23]]},"references-count":23,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["923"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0923-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,23]]}}}