EIBEN, Eduard, Robert GANIAN and Sebastian ORDYNIAK. A Structural Approach to Activity Selection. Online. In Jerome Lang. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI). USA: ijcai.org, 2018, p. 203-209. ISBN 978-0-9992411-2-7. Available from: https://dx.doi.org/10.24963/ijcai.2018/28.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name A Structural Approach to Activity Selection
Authors EIBEN, Eduard (703 Slovakia), Robert GANIAN (203 Czech Republic, guarantor, belonging to the institution) and Sebastian ORDYNIAK (276 Germany).
Edition USA, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI), p. 203-209, 7 pp. 2018.
Publisher ijcai.org
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
RIV identification code RIV/00216224:14330/18:00106815
Organization unit Faculty of Informatics
ISBN 978-0-9992411-2-7
ISSN 1045-0823
Doi http://dx.doi.org/10.24963/ijcai.2018/28
UT WoS 000764175400028
Keywords in English treewidth; computational social choice; group activity selection problem; parameterized complexity
Tags core_A, firank_1
Tags International impact, Reviewed
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 18/5/2022 10:35.
Abstract
The general task of finding an assignment of agents to activities under certain stability and rationality constraints has led to the introduction of two prominent problems in the area of computational social choice: Group Activity Selection (GASP) and Stable Invitations (SIP). Here we introduce and study the Comprehensive Activity Selection Problem, which naturally generalizes both of these problems. In particular, we apply the parameterized complexity paradigm, which has already been successfully employed for SIP and GASP. While previous work has focused strongly on parameters such as solution size or number of activities, here we focus on parameters which capture the complexity of agent-to-agent interactions. Our results include a comprehensive complexity map for CAS under various restrictions on the number of activities in combination with restrictions on the complexity of agent interactions.
PrintDisplayed: 5/7/2024 05:25