A Structural Approach to Activity Selection
Authors: Eduard Eiben, Robert Ganian, Sebastian Ordyniak
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | 1 Department of Informatics, University of Bergen, Norway 2 Algorithms and Complexity group, TU Wien, Austria 3 Algorithms group, University of Sheffield, UK |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. It provides 'Sketch of Proof' sections that describe algorithmic ideas but not formal pseudocode. |
| Open Source Code | No | The paper does not provide any statement about releasing source code or links to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on complexity analysis and algorithms. It does not describe any datasets used for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments that would require training, validation, or test data splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers for reproducing any computational results. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |