Group Activity Selection parameterized by the Number of Agent Types

Prelegent(ci)

Rahul CS

Afiliacja

Instytut Informatyki, UW

Termin

25 stycznia 2018 10:15

Pokój

p. 4790

Seminarium

Seminarium „Gry, mechanizmy i sieci społeczne”

---

We study the parameterized complexity of GASP (Group Activity Selection Problem) and its variant gGASP w.r.t. the number of different agent types as a parameter. We show that GASP can be solved in polynomial time if the number of agent types is a constant and complement this result with a strong parameterized hardness result, showing that GASP is unlikely to be fixed parameter tractable even when combining this parameter with the number of activities. In the case of gGASP we provide an even stronger hardness result showing that gGASP is unlikely to be fixed-parameter tractable parameterized by the number of agent types, the number of activities, and the vertex cover number of the network.

---