Group Activity Selection with Few Agent Types

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00113722" target="_blank" >RIV/00216224:14330/19:00113722 - isvavai.cz</a>

Výsledek na webu

<a href="https://drops.dagstuhl.de/opus/volltexte/2019/11169/" target="_blank" >https://drops.dagstuhl.de/opus/volltexte/2019/11169/</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ESA.2019.48" target="_blank" >10.4230/LIPIcs.ESA.2019.48</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Group Activity Selection with Few Agent Types

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Group Activity Selection with Few Agent Types

Popis výsledku anglicky

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.

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

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

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

27th Annual European Symposium on Algorithms (ESA 2019)

ISBN

9783959771245

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

16

Strana od-do

1-16

Název nakladatele

Dagstuhl

Místo vydání

Nemecko

Místo konání akce

Nemecko

Datum konání akce

1. 1. 2019

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

WRD - Celosvětová akce

Kód UT WoS článku

000570729400048