[Zurück]

E. Eiben, R. Ganian, S. Ordyniak:
"A Structural Approach to Activity Selection";
in: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence", herausgegeben von: IJCAI2018; International Joint Conferences on Artificial Intelligence, Stockholm, 2018, ISBN: 978-0-9992411-2-7, S. 203 - 209.

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.

https://publik.tuwien.ac.at/files/publik_276177.pdf