A Structural Approach to Activity Selection

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00106815" target="_blank" >RIV/00216224:14330/18:00106815 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.24963/ijcai.2018/28" target="_blank" >http://dx.doi.org/10.24963/ijcai.2018/28</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/ijcai.2018/28" target="_blank" >10.24963/ijcai.2018/28</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Structural Approach to Activity Selection

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

A Structural Approach to Activity Selection

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI)

ISBN

9780999241127

ISSN

1045-0823

e-ISSN

—

Počet stran výsledku

7

Strana od-do

203-209

Název nakladatele

ijcai.org

Místo vydání

USA

Místo konání akce

Svedsko

Datum konání akce

13. 7. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000764175400028