Group Activity Selection with Few Agent Types

D 2019

Group Activity Selection with Few Agent Types

GANIAN, Robert; Sebastian ORDYNIAK a C. S. RAHUL

Základní údaje

Originální název

Group Activity Selection with Few Agent Types

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí); Sebastian ORDYNIAK (276 Německo) a C. S. RAHUL (356 Indie)

Vydání

Nemecko, 27th Annual European Symposium on Algorithms (ESA 2019), od s. 1-16, 16 s. 2019

Nakladatel

Dagstuhl

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/19:00113722

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-124-5

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.ESA.2019.48

UT WoS

000570729400048

EID Scopus

2-s2.0-85074823509

Klíčová slova anglicky

Parameterized Complexity

Štítky

core_A, firank_A

Změněno: 16. 5. 2022 15:13, Mgr. Michal Petr

Anotace

V originále

The Group Activity Selection Problem (GASP) models situations where a group of agents needs to be distributed to a set of activities while taking into account preferences of the agents w.r.t. individual activities and activity sizes. The problem, along with its well-known variants sGASP and gGASP, has previously been studied in the parameterized complexity setting with various parameterizations, such as number of agents, number of activities and solution size. However, the complexity of the problem parameterized by the number of types of agents, a natural parameter proposed already in the first paper that introduced GASP, has so far remained unexplored. In this paper we establish the complexity map for GASP, sGASP and gGASP when the number of types of agents is the parameter. Our positive results, consisting of one fixed-parameter algorithm and one XP algorithm, rely on a combination of novel Subset Sum machinery (which may be of general interest) and identifying certain compression steps which allow us to focus on solutions which are "acyclic". These algorithms are complemented by matching lower bounds, which among others close a gap to a recently obtained tractability result of Gupta, Roy, Saurabh and Zehavi (2017). In this direction, the techniques used to establish W[1]-hardness of sGASP are of particular interest: as an intermediate step, we use Sidon sequences to show the W[1]-hardness of a highly restricted variant of multi-dimensional Subset Sum, which may find applications in other settings as well.

Citovat

GANIAN, Robert; Sebastian ORDYNIAK a C. S. RAHUL. Group Activity Selection with Few Agent Types. Online. In Michael A. Bender and Ola Svensson and Grzegorz Herman. 27th Annual European Symposium on Algorithms (ESA 2019). Nemecko: Dagstuhl, 2019, s. 1-16. ISBN 978-3-95977-124-5. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.ESA.2019.48.

@inproceedings{1648258,
   author = {Ganian, Robert and Ordyniak, Sebastian and Rahul, C. S.},
   address = {Nemecko},
   booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.ESA.2019.48},
   editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
   keywords = {Parameterized Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Nemecko},
   isbn = {978-3-95977-124-5},
   pages = {1-16},
   publisher = {Dagstuhl},
   title = {Group Activity Selection with Few Agent Types},
   url = {https://drops.dagstuhl.de/opus/volltexte/2019/11169/},
   year = {2019}
}

TY  - CONF
ID  - 1648258
AU  - Ganian, Robert - Ordyniak, Sebastian - Rahul, C. S.
PY  - 2019
TI  - Group Activity Selection with Few Agent Types
PB  - Dagstuhl
CY  - Nemecko
SN  - 9783959771245
KW  - Parameterized Complexity
UR  - https://drops.dagstuhl.de/opus/volltexte/2019/11169/
L2  - https://drops.dagstuhl.de/opus/volltexte/2019/11169/
N2  - The Group Activity Selection Problem (GASP) models situations where a group of agents needs to be distributed to a set of activities while taking into account preferences of the agents w.r.t. individual activities and activity sizes. The problem, along with its well-known variants sGASP and gGASP, has previously been studied in the parameterized complexity setting with various parameterizations, such as number of agents, number of activities and solution size. However, the complexity of the problem parameterized by the number of types of agents, a natural parameter proposed already in the first paper that introduced GASP, has so far remained unexplored. In this paper we establish the complexity map for GASP, sGASP and gGASP when the number of types of agents is the parameter. Our positive results, consisting of one fixed-parameter algorithm and one XP algorithm, rely on a combination of novel Subset Sum machinery (which may be of general interest) and identifying certain compression steps which allow us to focus on solutions which are "acyclic". These algorithms are complemented by matching lower bounds, which among others close a gap to a recently obtained tractability result of Gupta, Roy, Saurabh and Zehavi (2017). In this direction, the techniques used to establish W[1]-hardness of sGASP are of particular interest: as an intermediate step, we use Sidon sequences to show the W[1]-hardness of a highly restricted variant of multi-dimensional Subset Sum, which may find applications in other settings as well.
ER  -

GANIAN, Robert; Sebastian ORDYNIAK a C. S. RAHUL. Group Activity Selection with Few Agent Types. Online. In Michael A. Bender and Ola Svensson and Grzegorz Herman. \textit{27th Annual European Symposium on Algorithms (ESA 2019)}. Nemecko: Dagstuhl, 2019, s.~1-16. ISBN~978-3-95977-124-5. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.ESA.2019.48.

Přehled o publikaci