A General Framework for Stable Roommates Problems using Answer Set Programming
From MaRDI portal
Abstract: 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. This paper is under consideration for acceptance in TPLP.
Recommendations
- Stable Roommates and Constraint Programming
- The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
- An efficient algorithm for the “stable roommates” problem
- On a generalization of the stable roommates problem
- The stable fixtures problem -- a many-to-many extension of stable roommates
- An algorithm for a super-stable roommates problem
- Solving stable matching problems using answer set programming
- An approach to robustness in the stable roommates problem and its comparison with the stable marriage problem
- A maximum stable matching for the roommates problem
Cites work
- ``Almost stable matchings in the roommates problem with bounded preference lists
- A new fixed point approach for stable networks and stable marriages
- An efficient algorithm for the “stable roommates” problem
- Approximation and Online Algorithms
- College Admissions and the Stability of Marriage
- Complete extensions in argumentation coincide with 3-valued stable models in logic programming
- Extending and implementing the stable model semantics
- Geometric stable roommates
- scientific article; zbMATH DE number 5914356 (Why is no real title available?)
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 25190 (Why is no real title available?)
- scientific article; zbMATH DE number 45086 (Why is no real title available?)
- scientific article; zbMATH DE number 1369412 (Why is no real title available?)
- scientific article; zbMATH DE number 5212421 (Why is no real title available?)
- NP-complete stable matching problems
- On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games
- Pairwise kidney exchange
- Random stable matchings
- Stable marriage and indifference
- Stable marriage with ties and bounded length preference lists
- Stable Roommates and Constraint Programming
- The stable roommates problem with short lists
- The Stable Roommates Problem with Ties
- The strongly stable roommates problem
- Tight logic programs
Cited in
(4)
This page was built for publication: A General Framework for Stable Roommates Problems using Answer Set Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140025)
