{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T22:35:11Z","timestamp":1743028511453,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":24,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_677","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:06Z","timestamp":1461268986000},"page":"1227-1230","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximum Cardinality Stable Matchings"],"prefix":"10.1007","author":[{"given":"Eric","family":"McDermid","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"217_CR13161","unstructured":"Dean B, Jalasutram R (2015, to appear) Factor revealing LPs and stable matching with ties and incomplete lists. In: Proceedings of MATCH-UP 2015: the 3rd international workshop on matching under preferences, Glasgow"},{"key":"217_CR13162","doi-asserted-by":"publisher","first-page":"9","DOI":"10.2307\/2312726","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Mon 69:9\u201315","journal-title":"Am Math Mon"},{"key":"217_CR13163","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson MM, Iwama K, Miyazaki S, Yanagisawa H (2003) Improved approximation of the stable marriage problem. In: Proceedings of ESA 2003: the 11th annual European symposium on algorithms, Budapest. Lecture notes in computer science, vol\u00a02832. Springer, pp\u00a0266\u2013277","DOI":"10.1007\/978-3-540-39658-1_26"},{"issue":"3","key":"217_CR13164","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/j.tcs.2004.02.045","volume":"325","author":"MM Halld\u00f3rsson","year":"2004","unstructured":"Halld\u00f3rsson MM, Iwama K, Miyazaki S, Yanagisawa H (2004) Randomized approximation of the stable marriage problem. Theor Comput Sci 325(3):439\u2013465","journal-title":"Theor Comput Sci"},{"key":"217_CR13165","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson M, Iwama K, Miyazaki S, Yanagisawa H (2007) Improved approximation of the stable marriage problem. ACM Trans Algorithms 3(3):30-es","DOI":"10.1145\/1273340.1273346"},{"key":"217_CR13166","unstructured":"http:\/\/www.jrmp.jp (Japan Resident Matching Program website)"},{"key":"217_CR13167","unstructured":"http:\/\/www.nrmp.org (National Resident Matching Program website)"},{"key":"217_CR13168","unstructured":"http:\/\/www.carms.ca (Canadian Resident Matching Service website)"},{"key":"217_CR13169","unstructured":"http:\/\/www.nes.scot.nhs.uk\/sfas (Scottish Foundation Allocation Scheme website)"},{"key":"217_CR13170","doi-asserted-by":"crossref","unstructured":"Huang C-C, Kavitha T (2014) An improved approximation algorithm for the stable marriage problem with one-sided ties. In: Proceedings of IPCO 2014, the 17th conference on integer programming and combinatorial optimization, Bonn. Lecture notes in computer science, vol\u00a08494. Springer, pp\u00a0297\u2013308","DOI":"10.1007\/978-3-319-07557-0_25"},{"issue":"3","key":"217_CR13171","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10878-007-9133-x","volume":"16","author":"RW Irving","year":"2008","unstructured":"Irving RW, Manlove D (2008) Approximation algorithms for hard variants of the stable marriage and hospitals\/residents problem. J Comb Optim 16(3):279\u2013292","journal-title":"J Comb Optim"},{"key":"217_CR13172","unstructured":"Iwama K, Miyazaki S, Okamoto K (2004) A 2 \u2212 c log n n $$\\left (2 - c\\frac{\\log n} {n}\\right )$$ -approximation algorithm for the stable marriage problem. In: Proceedings of SWAT 2004: the 9th Scandinavian workshop on algorithm theory, Humlebaek. Lecture notes in computer science, vol\u00a03111. Springer, pp\u00a0349\u2013361"},{"key":"217_CR13173","unstructured":"Iwama K, Miyazaki S, Yamauchi N (2007) A 1.875-approximation algorithm for the stable marriage problem. In: Proceedings of SODA 2007: the eighteenth ACM\/SIAM symposium on discrete algorithms, New Orleans, pp\u00a0288\u2013297"},{"issue":"3","key":"217_CR13174","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/s00453-007-9101-y","volume":"51","author":"K Iwama","year":"2008","unstructured":"Iwama K, Miyazaki S, Yamauchi N (2008) A 2 \u2212 c 1 n $$\\left (2 - c \\frac{1} {\\sqrt{n}}\\right )$$ -approximation algorithm for the stable marriage problem. Algorithmica 51(3):342\u2013356","journal-title":"Algorithmica"},{"key":"217_CR13175","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/s00453-012-9699-2","volume":"68","author":"K Iwama","year":"2014","unstructured":"Iwama K, Miyazaki S, Yanagisawa H (2014) A 25\/17-approximation algorithm for the stable marriage problem with one-sided ties. Algorithmica 68:758\u2013775","journal-title":"Algorithmica"},{"issue":"1","key":"217_CR13176","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-009-9371-7","volume":"60","author":"Z Kir\u00e1ly","year":"2011","unstructured":"Kir\u00e1ly Z (2011) Better and simpler approximation algorithms for the stable marriage problem. Algorithmica 60(1):3\u201320","journal-title":"Algorithmica"},{"issue":"3","key":"217_CR13177","doi-asserted-by":"publisher","first-page":"471","DOI":"10.3390\/a6030471","volume":"6","author":"Z Kir\u00e1ly","year":"2013","unstructured":"Kir\u00e1ly Z (2013) Linear time local approximation algorithm for maximum stable marriage. MDPI Algorithms 6(3):471\u2013484","journal-title":"MDPI Algorithms"},{"key":"217_CR13178","volume-title":"Mariages stables","author":"DE Knuth","year":"1976","unstructured":"Knuth DE (1976) Mariages stables. Les Presses de L\u2019Universit\u00e9 de Montr\u00e9al, Montr\u00e9al"},{"key":"217_CR13179","doi-asserted-by":"publisher","DOI":"10.1142\/8591","volume-title":"Algorithmics of matching under preferences","author":"D Manlove","year":"2013","unstructured":"Manlove D (2013) Algorithmics of matching under preferences. World Scientific, Hackensack"},{"issue":"1\u20132","key":"217_CR13180","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","volume":"276","author":"DF Manlove","year":"2002","unstructured":"Manlove DF, Irving RW, Iwama K, Miyazaki S, Morita Y (2002) Hard variants of stable marriage. Theor Comput Sci 276(1\u20132):261\u2013279","journal-title":"Theor Comput Sci"},{"key":"217_CR13181","doi-asserted-by":"crossref","unstructured":"McDermid EJ (2009) A 3\/2-approximation algorithm for general stable marriage. In: Proceedings of ICALP 2009: the 36th international colloquium on automata, languages and programming, Rhodes. Lecture notes in computer science, vol\u00a05555. Springer, pp\u00a0689\u2013700","DOI":"10.1007\/978-3-642-02927-1_57"},{"issue":"2","key":"217_CR13182","doi-asserted-by":"publisher","first-page":"189","DOI":"10.3390\/a7020189","volume":"7","author":"KE Paluch","year":"2014","unstructured":"Paluch KE (2014) Faster and simpler approximation of stable matchings. MDPI Algorithms 7(2): 189\u2013202","journal-title":"MDPI Algorithms"},{"key":"217_CR13183","volume-title":"Approximation algorithms for the stable matching problem","author":"A Radnai","year":"2014","unstructured":"Radnai A (2014) Approximation algorithms for the stable matching problem. Master\u2019s thesis, E\u00f6tv\u00f6s Lor\u00e1nd University"},{"key":"217_CR13184","unstructured":"Yanagisawa H (2007) Approximation algorithms for stable marriage problems. PhD thesis, School of Informatics, Kyoto University"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_677","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T19:05:42Z","timestamp":1567796742000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_677"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_677","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}