GANIAN, Robert, Sebastian ORDYNIAK and 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, p. 1-16. ISBN 978-3-95977-124-5. Available from: https://dx.doi.org/10.4230/LIPIcs.ESA.2019.48.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Group Activity Selection with Few Agent Types
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Sebastian ORDYNIAK (276 Germany) and C. S. RAHUL (356 India).
Edition Nemecko, 27th Annual European Symposium on Algorithms (ESA 2019), p. 1-16, 16 pp. 2019.
Publisher Dagstuhl
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
RIV identification code RIV/00216224:14330/19:00113722
Organization unit Faculty of Informatics
ISBN 978-3-95977-124-5
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.ESA.2019.48
UT WoS 000570729400048
Keywords in English Parameterized Complexity
Tags core_A, firank_A
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 16/5/2022 15:13.
Abstract
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.
PrintDisplayed: 5/5/2024 09:34