Parameterized Complexity of Caching in Networks
Authors: Robert Ganian, Fionn Mc Inerney, Dimitra Tsigkari
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We close this gap by performing a comprehensive complexity-theoretic analysis of the problem through the lens of the parameterized complexity paradigm, which is designed to provide more precise statements regarding algorithmic tractability than classical complexity. Our results include algorithmic lower and upper bounds which together establish the conditions under which the caching problem becomes tractable. |
| Researcher Affiliation | Collaboration | Robert Ganian1, Fionn Mc Inerney2, Dimitra Tsigkari2 1Algorithms and Complexity Group, TU Wien, Vienna, Austria 2Telef onica Scientific Research, Barcelona, Spain EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper describes algorithms (e.g., in Theorem 3's proof sketch) but does not present them in a structured pseudocode block or algorithm figure format. |
| Open Source Code | No | The paper does not provide any concrete access information for source code, such as a repository link, explicit code release statement, or mention of code in supplementary materials. |
| Open Datasets | No | The paper is theoretical and analyzes the complexity of the NETWORK-CACHING problem; it does not present any empirical studies using specific datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments requiring dataset splits. |
| Hardware Specification | No | The paper presents theoretical complexity analysis and does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper focuses on theoretical complexity analysis and does not mention any specific software dependencies with version numbers for experimental implementation. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details, hyperparameters, or training configurations. |