{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T06:42:34Z","timestamp":1725864154636},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662533536"},{"type":"electronic","value":"9783662533543"}],"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":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53354-3_17","type":"book-chapter","created":{"date-parts":[[2016,9,3]],"date-time":"2016-09-03T22:43:34Z","timestamp":1472942614000},"page":"207-219","source":"Crossref","is-referenced-by-count":0,"title":["The Stable Roommates Problem with Short Lists"],"prefix":"10.1007","author":[{"given":"\u00c1gnes","family":"Cseh","sequence":"first","affiliation":[]},{"given":"Robert W.","family":"Irving","sequence":"additional","affiliation":[]},{"given":"David F.","family":"Manlove","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,1]]},"reference":[{"key":"17_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/11774129","volume-title":"Approximation and Online Algorithms","author":"DJ Abraham","year":"2006","unstructured":"Abraham, D.J., Bir\u00f3, P., Manlove, D.F.: \u201cAlmost Stable\u201d matchings in the roommates problem. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol. 3879, pp. 1\u201314. Springer, Heidelberg (2006)"},{"key":"17_CR2","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. ECCC report, no. 49 (2003)"},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.tcs.2012.01.022","volume":"432","author":"P Bir\u00f3","year":"2012","unstructured":"Bir\u00f3, P., Manlove, D.F., McDermid, E.J.: \u201cAlmost stable\" matchings in the roommates problem with bounded preference lists. Theor. Comput. Sci. 432, 10\u201320 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"1828","DOI":"10.1016\/j.tcs.2010.02.003","volume":"411","author":"P Bir\u00f3","year":"2010","unstructured":"Bir\u00f3, P., Manlove, D.F., McDermid, E.J.: Almost stable matchings in the roommates problem with bounded preference lists. Theor. Comput. Sci. 411, 1828\u20131841 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR5","unstructured":"Cseh, \u00c1., Irving, R.W., Manlove, D.F.: The stable roommates problem with short lists. CoRR abs\/1605.04609 (2016). http:\/\/arxiv.org\/abs\/1605.04609"},{"key":"17_CR6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0022-0000(92)90048-N","volume":"45","author":"T Feder","year":"1992","unstructured":"Feder, T.: A new fixed point approach for stable networks and stable marriages. J. Comput. Syst. Sci. 45, 233\u2013284 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR7","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF01240738","volume":"11","author":"T Feder","year":"1994","unstructured":"Feder, T.: Network flow and 2-satisfiability. Algorithmica 11, 291\u2013319 (1994)","journal-title":"Algorithmica"},{"key":"17_CR8","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. Monthly 69, 9\u201315 (1962)","journal-title":"Am. Math. Monthly"},{"issue":"1","key":"17_CR9","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0216010","volume":"16","author":"D Gusfield","year":"1987","unstructured":"Gusfield, D.: Three fast algorithms for four problems in stable marriage. SIAM J. Comput. 16(1), 111\u2013128 (1987)","journal-title":"SIAM J. Comput."},{"key":"17_CR10","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, Cambridge (1989)"},{"key":"17_CR11","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/BF01758838","volume":"8","author":"D Gusfield","year":"1992","unstructured":"Gusfield, D., Pitt, L.: A bounded approximation for the minimum cost 2-SAT problem. Algorithmica 8, 103\u2013117 (1992)","journal-title":"Algorithmica"},{"key":"17_CR12","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1016\/j.ipl.2009.06.008","volume":"109","author":"K Hamada","year":"2009","unstructured":"Hamada, K., Iwama, K., Miyazaki, S.: An improved approximation lower bound for finding almost stable maximum matchings. Inf. Process. Lett. 109, 1036\u20131040 (2009)","journal-title":"Inf. Process. Lett."},{"key":"17_CR13","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1016\/0196-6774(85)90033-1","volume":"6","author":"RW Irving","year":"1985","unstructured":"Irving, R.W.: An efficient algorithm for the \"stable roommates\" problem. J. Algorithms 6, 577\u2013595 (1985)","journal-title":"J. Algorithms"},{"key":"17_CR14","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1145\/28869.28871","volume":"34","author":"RW Irving","year":"1987","unstructured":"Irving, R.W., Leather, P., Gusfield, D.: An efficient algorithm for the \u201coptimal\" stable marriage. J. ACM 34, 532\u2013543 (1987)","journal-title":"J. ACM"},{"key":"17_CR15","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/jagm.2002.1219","volume":"43","author":"RW Irving","year":"2002","unstructured":"Irving, R.W., Manlove, D.F.: The stable roommates problem with ties. J. Algorithms 43, 85\u2013105 (2002)","journal-title":"J. Algorithms"},{"key":"17_CR16","first-page":"19","volume":"7","author":"E Kujansuu","year":"1999","unstructured":"Kujansuu, E., Lindberg, T., M\u00e4kinen, E.: The stable roommates problem and chess tournament pairings. Divulgaciones Matem\u00e1ticas 7, 19\u201328 (1999)","journal-title":"Divulgaciones Matem\u00e1ticas"},{"key":"17_CR17","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- $$\\varepsilon $$ . J. Comput. Syst. Sci. 74, 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR18","doi-asserted-by":"crossref","DOI":"10.1142\/8591","volume-title":"Algorithmics of Matching Under Preferences","author":"DF Manlove","year":"2013","unstructured":"Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific, Singapore (2013)"},{"key":"17_CR19","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","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, 261\u2013279 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR20","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0196-6774(90)90007-2","volume":"11","author":"E Ronn","year":"1990","unstructured":"Ronn, E.: NP-complete stable matching problems. J. Algorithms 11, 285\u2013304 (1990)","journal-title":"J. Algorithms"},{"key":"17_CR21","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/0196-6774(91)90028-W","volume":"12","author":"JJM Tan","year":"1991","unstructured":"Tan, J.J.M.: A necessary and sufficient condition for the existence of a complete stable matching. J. Algorithms 12, 154\u2013178 (1991)","journal-title":"J. Algorithms"},{"key":"17_CR22","unstructured":"Teo, C.-P., Sethuraman, J.: LP based approach to optimal stable matchings. In: Proceedings of SODA 1997, pp. 710\u2013719. ACM-SIAM (1997)"},{"key":"17_CR23","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, 874\u2013891 (1998)","journal-title":"Math. Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53354-3_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T21:59:49Z","timestamp":1498341589000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53354-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662533536","9783662533543"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53354-3_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}