{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T10:59:31Z","timestamp":1772017171350,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,9,30]],"date-time":"2017-09-30T00:00:00Z","timestamp":1506729600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["Momentum Programme (LP2016-3\/2016)"],"award-info":[{"award-number":["Momentum Programme (LP2016-3\/2016)"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["J\u00e1nos Bolyai Research Fellowship"],"award-info":[{"award-number":["J\u00e1nos Bolyai Research Fellowship"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003827","name":"Nemzeti Kutat\u00e1si \u00e9s Technol\u00f3giai Hivatal","doi-asserted-by":"publisher","award":["OTKA K108383"],"award-info":[{"award-number":["OTKA K108383"]}],"id":[{"id":"10.13039\/501100003827","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K010042\/1"],"award-info":[{"award-number":["EP\/K010042\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000921","name":"European Cooperation in Science and Technology","doi-asserted-by":"publisher","award":["IC1205"],"award-info":[{"award-number":["IC1205"]}],"id":[{"id":"10.13039\/501100000921","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,1]]},"DOI":"10.1007\/s00224-017-9810-9","type":"journal-article","created":{"date-parts":[[2017,9,30]],"date-time":"2017-09-30T00:40:50Z","timestamp":1506732050000},"page":"128-149","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["The Stable Roommates Problem with Short Lists"],"prefix":"10.1007","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4991-2599","authenticated-orcid":false,"given":"\u00c1gnes","family":"Cseh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert W.","family":"Irving","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David F.","family":"Manlove","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,30]]},"reference":[{"key":"9810_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, D J., Bir\u00f3, P., Manlove, D.F.: \u201cAlmost stable\u201d matchings in the roommates problem. In: Proceedings of WAOA \u201905, vol. 3879 of Lecture Notes in Computer Science, pp 1\u201314. Springer, Berlin (2006)","DOI":"10.1007\/11671411_1"},{"key":"9810_CR2","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. ECCC report, no. 49 (2003)"},{"key":"9810_CR3","doi-asserted-by":"crossref","unstructured":"Bir\u00f3 P., Manlove, D.F., McBride, I.: The Hospitals \/ Residents problem with couples: Complexity and integer programming models. In: Proceedings of SEA \u201914, vol. 8504 of Lecture Notes in Computer Science, pp 10\u201321. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-07959-2_2"},{"key":"9810_CR4","doi-asserted-by":"publisher","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\u201d matchings in the roommates problem with bounded preference lists. Theor. Comput. Sci. 432, 10\u201320 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"9810_CR5","doi-asserted-by":"publisher","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., Mittal, S.: Size versus stability in the marriage problem. Theor. Comput. Sci. 411, 1828\u20131841 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9810_CR6","unstructured":"Chen, J., Hermelin, D., Sorge, M., Yedidsion, H.: How hard is it to satisfy (almost) all roommates? arXiv: 1707.04316 (2017)"},{"key":"9810_CR7","doi-asserted-by":"publisher","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":"9810_CR8","doi-asserted-by":"publisher","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":"9810_CR9","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Amer. Math. Month. 69, 9\u201315 (1962)","journal-title":"Amer. Math. Month."},{"key":"9810_CR10","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9810_CR11","doi-asserted-by":"publisher","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":"9810_CR12","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":"9810_CR13","doi-asserted-by":"publisher","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":"9810_CR14","doi-asserted-by":"publisher","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":"9810_CR15","doi-asserted-by":"publisher","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 \u201cstable roommates\u201d problem. J. Algor. 6, 577\u2013595 (1985)","journal-title":"J. Algor."},{"key":"9810_CR16","doi-asserted-by":"publisher","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\u201d stable marriage. J. ACM 34, 532\u2013543 (1987)","journal-title":"J. ACM"},{"key":"9810_CR17","doi-asserted-by":"publisher","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. Algor. 43, 85\u2013105 (2002)","journal-title":"J. Algor."},{"key":"9810_CR18","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":"9810_CR19","doi-asserted-by":"publisher","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- \u03b5. J. Comput. Syst. Sci. 74, 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"9810_CR20","unstructured":"Maier, D., Storer, J.: A note on the complexity of the superstring problem Technical Report 233, Princeton University, Department of Electrical Engineering and Computer Science, Princeton, NJ (1977)"},{"key":"9810_CR21","doi-asserted-by":"publisher","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":"9810_CR22","doi-asserted-by":"publisher","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":"9810_CR23","doi-asserted-by":"publisher","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. Algor. 11, 285\u2013304 (1990)","journal-title":"J. Algor."},{"key":"9810_CR24","doi-asserted-by":"publisher","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. Algor. 12, 154\u2013178 (1991)","journal-title":"J. Algor."},{"key":"9810_CR25","unstructured":"Teo, C-P, Sethuraman, J: LP based approach to optimal stable matchings. In: Proceedings of SODA \u201997, pp 710\u2013719. ACM-SIAM, New York (1997)"},{"key":"9810_CR26","doi-asserted-by":"publisher","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":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9810-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9810-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9810-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T23:58:12Z","timestamp":1570147092000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9810-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,30]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["9810"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9810-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,30]]},"assertion":[{"value":"30 September 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}