{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,14]],"date-time":"2026-08-14T10:09:06Z","timestamp":1786702146929,"version":"build-2736575974"},"reference-count":39,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T00:00:00Z","timestamp":1600732800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Stable Roommates problem (SR) is characterized by the preferences of agents over other agents as roommates: each agent ranks all others in strict order of preference. A solution to SR is then a partition of the agents into pairs so that each pair shares a room, and there is no pair of agents that would block this matching (i.e., who prefers the other to their roommate in the matching). There are interesting variations of SR that are motivated by applications (e.g., the preference lists may be incomplete (SRI) and involve ties (SRTI)), and that try to find a more fair solution (e.g., Egalitarian SR). Unlike the Stable Marriage problem, every SR instance is not guaranteed to have a solution. For that reason, there are also variations of SR that try to find a good-enough solution (e.g., Almost SR). Most of these variations are NP-hard. We introduce a formal framework, called SRTI-ASP, utilizing the logic programming paradigm Answer Set Programming, that is provable and general enough to solve many of such variations of SR. Our empirical analysis shows that SRTI-ASP is also promising for applications.<\/jats:p>","DOI":"10.1017\/s1471068420000277","type":"journal-article","created":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T02:43:15Z","timestamp":1600742595000},"page":"911-925","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["A General Framework for Stable Roommates Problems using Answer Set Programming"],"prefix":"10.1017","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8384-7810","authenticated-orcid":false,"given":"ESRA","family":"ERDEM","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M\u00dcGE","family":"FIDAN","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"DAVID","family":"MANLOVE","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"PATRICK","family":"PROSSER","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2020,9,22]]},"reference":[{"key":"S1471068420000277_ref23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/jagm.2002.1219","article-title":"The stable roommates problem with ties","volume":"1","author":"Irving","year":"2002","journal-title":"Journal of Algorithms 43"},{"key":"S1471068420000277_ref10","first-page":"321","article-title":"On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games","volume":"2","author":"Dung","year":"1995","journal-title":"AIJ 77"},{"key":"S1471068420000277_ref12","doi-asserted-by":"crossref","unstructured":"12. Erdogan, S. T. and Lifschitz, V. 2004. Definitions in answer set programming. In Proc. of LPNMR.","DOI":"10.1007\/978-3-540-24599-5_34"},{"key":"S1471068420000277_ref20","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"Gusfield","year":"1989"},{"key":"S1471068420000277_ref29","unstructured":"29. Manlove, D. 1999. Stable marriage with ties and unacceptable partners."},{"key":"S1471068420000277_ref3","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.ipl.2008.10.003","article-title":"Geometric stable roommates","volume":"4","author":"Arkin","year":"2009","journal-title":"Inf. Process. Lett. 109,"},{"key":"S1471068420000277_ref7","unstructured":"7. Cooper, F. 2020. Fair and large stable matchings in the stable marriage and student-project allocation problems. Ph.D. thesis, University of Glasgow."},{"key":"S1471068420000277_ref17","doi-asserted-by":"crossref","first-page":"107","DOI":"10.3233\/AIC-2011-0491","article-title":"Potassco: The Potsdam Answer Set Solving Collection","volume":"2","author":"Gebser","year":"2011","journal-title":"AI Communications 24"},{"key":"S1471068420000277_ref27","unstructured":"27. Kunysz, A. 2016. The Strongly Stable Roommates Problem. In Proc. of ESA. Vol. 57. 60:1\u201360:15."},{"key":"S1471068420000277_ref13","unstructured":"13. Erd\u00f6s, P. and R\u00e9nyi, A. 1960. On the evolution of random graphs. In Publication of the Mathematical Institute of the Hungarian Academy of Sciences. 17\u201361."},{"key":"S1471068420000277_ref1","volume-title":"International Workshop on Approximation and Online Algorithms","author":"Abraham","year":"2005"},{"key":"S1471068420000277_ref4","unstructured":"4. Bir\u00f3, P. , Manlove, D. F. , and McDermid, E. J. 2012. \u201cAlmost stable\u201d matchings in the roommates problem with bounded preference lists. Theoretical Computer Science 432, 10\u201320."},{"key":"S1471068420000277_ref34","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0196-6774(90)90007-2","article-title":"Np-complete stable matching problems","volume":"2","author":"Ronn","year":"1990","journal-title":"Journal of Algorithms 11"},{"key":"S1471068420000277_ref18","unstructured":"18. Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of ICLP. 1070\u20131080."},{"key":"S1471068420000277_ref28","unstructured":"28. Lifschitz, V. and Turner, H. 1994. Splitting a logic program. In Proc. of ICLP. 23\u201337."},{"key":"S1471068420000277_ref37","first-page":"181","article-title":"Extending and implementing the stable model semantics","volume":"1","author":"Simons","year":"2002","journal-title":"AIJ 138"},{"key":"S1471068420000277_ref25","unstructured":"25. Knuth, D. 1997. Stable marriage and its relation to other combinatorial problems: an introduction to the mathematical analysis of algorithms. In Volume 10 of CRM Proc. Mariages Stables (in English), 1976."},{"key":"S1471068420000277_ref39","doi-asserted-by":"publisher","DOI":"10.1007\/s11225-009-9210-5"},{"key":"S1471068420000277_ref33","doi-asserted-by":"crossref","unstructured":"33. Prosser, P. 2014. Stable roommates and constraint programming. In Proc. of CPAIOR. 15\u201328.","DOI":"10.1007\/978-3-319-07046-9_2"},{"key":"S1471068420000277_ref19","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF03037169","article-title":"Classical negation in logic programs and disjunctive databases","author":"Gelfond","year":"1991","journal-title":"New Generation Computing 9"},{"key":"S1471068420000277_ref11","first-page":"499","article-title":"Tight logic programs","volume":"4","author":"Erdem","year":"2003","journal-title":"TPLP 3"},{"key":"S1471068420000277_ref31","unstructured":"31. McCarthy, J. 1998. Elaboration tolerance. In Proc. of CommonSense."},{"key":"S1471068420000277_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00179-P"},{"key":"S1471068420000277_ref15","unstructured":"15. Gai, A.-T. , Mathieu, F. , de Montgolfier, F. , and Reynier, J. 2007. Stratification in P2P networks: Application to BitTorrent. In Proc. of ICDCS. 30."},{"key":"S1471068420000277_ref16","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","article-title":"College admissions and the stability of marriage","volume":"1","author":"Gale","year":"1962","journal-title":"The American Mathematical Monthly 69"},{"key":"S1471068420000277_ref26","first-page":"19","article-title":"The stable roomates problem and chess tournament pairings","author":"Kujansuu","year":"1999","journal-title":"Divulgaciones Matem\u00e1ticas 7"},{"key":"S1471068420000277_ref36","unstructured":"36. Scott, S. 2005. A study of stable marriage problems with ties. Ph.D. thesis, University of Glasgow."},{"key":"S1471068420000277_ref32","doi-asserted-by":"crossref","first-page":"P10008","DOI":"10.1088\/1742-5468\/2005\/10\/P10008","article-title":"Random stable matchings","volume":"10","author":"Mertens","year":"2005","journal-title":"Journal of Statistical Mechanics: Theory and Experiment 2005"},{"key":"S1471068420000277_ref24","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.jda.2008.09.003","article-title":"Stable marriage with ties and bounded length preference lists","volume":"2","author":"Irving","year":"2009","journal-title":"Journal of Discrete Algorithms 7"},{"key":"S1471068420000277_ref5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1609\/aimag.v37i3.2669","article-title":"Answer set programming: An introduction to the special issue","volume":"3","author":"Brewka","year":"2016","journal-title":"AI Magazine 37"},{"key":"S1471068420000277_ref9","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/502807.502810","article-title":"Complexity and expressive power of logic programming","volume":"3","author":"Dantsin","year":"2001","journal-title":"ACM Comput. Surv. 33"},{"key":"S1471068420000277_ref6","unstructured":"6. Buccafurri, F. , Leone, N. , and Rullo, P. 2000. Enhancing disjunctive datalog by constraints. IEEE Trans. Knowl. Data Eng. 12, 5, 845\u2013860."},{"key":"S1471068420000277_ref2","unstructured":"2. Amendola, G. 2018. Solving the stable roommates problem using incoherent answer set programs. In Proc. of RiCeRcA."},{"key":"S1471068420000277_ref14","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0022-0000(92)90048-N","article-title":"A new fixed point approach for stable networks and stable marriages","volume":"2","author":"Feder","year":"1992","journal-title":"Journal of Computer and System Sciences 45"},{"key":"S1471068420000277_ref8","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/s00224-017-9810-9","article-title":"The stable roommates problem with short lists","volume":"1","author":"Cseh","year":"2019","journal-title":"Theory of Computing Systems 63"},{"key":"S1471068420000277_ref35","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/j.jet.2005.04.004","article-title":"Pairwise kidney exchange","volume":"2","author":"Roth","year":"2005","journal-title":"Journal of Economic Theory 125"},{"key":"S1471068420000277_ref30","unstructured":"30. MatchingToolkit. 2020. http:\/\/matwa.optimalmatching.com\/."},{"key":"S1471068420000277_ref38","unstructured":"38. SRItoolkit. 2019. http:\/\/www.dcs.gla.ac.uk\/ pat\/roommates\/distribution\/ (2019-11-21)."},{"key":"S1471068420000277_ref21","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1016\/0196-6774(85)90033-1","article-title":"An efficient algorithm for the \u201cstable roommates\u201d problem","volume":"4","author":"Irving","year":"1985","journal-title":"Journal of Algorithms 6"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068420000277","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T10:47:56Z","timestamp":1603104476000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068420000277\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,22]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["S1471068420000277"],"URL":"https:\/\/doi.org\/10.1017\/s1471068420000277","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,22]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}