论文标题
使用答案集编程的稳定室友问题的一般框架
A General Framework for Stable Roommates Problems using Answer Set Programming
论文作者
论文摘要
稳定的室友问题（SR）的特征是代理人比其他代理人的偏好为室友：每个代理都以严格的优先顺序对所有其他代理进行排名。然后，对SR的解决方案是将代理分成对的，以便每对共享一个房间，并且没有一对代理会阻止这种匹配（即，在匹配中更喜欢对方的室友）。 SR的有趣变化是由应用程序激励的（例如，偏好列表可能不完整（SRI）并涉及联系（SRTI）），并尝试找到更公平的解决方案（例如，Egalitarian SR）。与稳定的婚姻问题不同，每个SR实例都不能保证有解决方案。因此，SR也有一些变化，它们试图找到一个很好的溶液（例如，几乎是SR）。这些变体大多数都是NP-HARD。我们介绍了一个名为SRTI-ASP的正式框架，利用了逻辑编程范式答案集编程，该编程是可证明的，足以解决SR的许多此类变化。我们的经验分析表明，SRTI-ASP对于应用也很有希望。本文正在考虑在TPLP中接受。
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.
