The Complexity of Optimizing Atomic Congestion
Authors: Cornelius Brand, Robert Ganian, Subrahmanyam Kalyanasundaram, Fionn Mc Inerney
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The Complexity of Optimizing Atomic Congestion...We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem. |
| Researcher Affiliation | Academia | 1Algorithms & Complexity Theory Group, Regensburg University, Germany 2Algorithms and Complexity Group, TU Wien, Austria 3Department of Computer Science and Engineering, IIT Hyderabad, India |
| Pseudocode | No | The paper describes algorithms and their logic (e.g., dynamic programming procedure in Theorem 5 Proof Sketch) but does not provide formal pseudocode blocks or labeled algorithm sections. |
| Open Source Code | No | The paper does not provide any statement or link indicating the release of source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with datasets, thus no information about public datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with datasets, thus no information about training/validation/test splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not conduct experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not conduct experiments, thus no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity analysis and algorithm design, not empirical experimentation. Therefore, no experimental setup details like hyperparameters are provided. |