A Structural Approach to Activity Selection

D 2018

A Structural Approach to Activity Selection

EIBEN, Eduard, Robert GANIAN a Sebastian ORDYNIAK

Základní údaje

Originální název

A Structural Approach to Activity Selection

Autoři

EIBEN, Eduard (703 Slovensko), Robert GANIAN (203 Česká republika, garant, domácí) a Sebastian ORDYNIAK (276 Německo)

Vydání

USA, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI), od s. 203-209, 7 s. 2018

Nakladatel

ijcai.org

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/18:00106815

Organizační jednotka

Fakulta informatiky

ISBN

978-0-9992411-2-7

ISSN

DOI

http://dx.doi.org/10.24963/ijcai.2018/28

UT WoS

000764175400028

Klíčová slova anglicky

treewidth; computational social choice; group activity selection problem; parameterized complexity

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 18. 5. 2022 10:35, Mgr. Michal Petr

Anotace

V originále

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.

Citovat

EIBEN, Eduard, Robert GANIAN a 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, s. 203-209. ISBN 978-0-9992411-2-7. Dostupné z: https://dx.doi.org/10.24963/ijcai.2018/28.

@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 a 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, s.~203-209. ISBN~978-0-9992411-2-7. Dostupné z: https://dx.doi.org/10.24963/ijcai.2018/28.

Podrobný výpis o publikaci