Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1523779, author = {Eiben, Eduard and Ganian, Robert and Ordyniak, Sebastian}, address = {USA}, booktitle = {Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI)}, doi = {http://dx.doi.org/10.24963/ijcai.2018/28}, editor = {Jerome Lang}, keywords = {treewidth; computational social choice; group activity selection problem; parameterized complexity}, howpublished = {elektronická verze "online"}, language = {eng}, location = {USA}, isbn = {978-0-9992411-2-7}, pages = {203-209}, publisher = {ijcai.org}, title = {A Structural Approach to Activity Selection}, year = {2018} }
TY - JOUR ID - 1523779 AU - Eiben, Eduard - Ganian, Robert - Ordyniak, Sebastian PY - 2018 TI - A Structural Approach to Activity Selection PB - ijcai.org CY - USA SN - 9780999241127 KW - treewidth KW - computational social choice KW - group activity selection problem KW - parameterized complexity N2 - 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. ER -
EIBEN, Eduard, Robert GANIAN and Sebastian ORDYNIAK. A Structural Approach to Activity Selection. Online. In Jerome Lang. \textit{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.
|