Approximating Optimal Labelings for Temporal Connectivity
Authors: Daniele Carnevale, Gianlorenzo D'Angelo, Martin Olsen
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our results. We provide both hardness of approximation lower-bounds and approximation algorithms for MAL. Hardness of approximation. We first prove that, even when the maximum allowed age a of a labeling is a fixed value greater or equal to 2, MAL cannot be approximated within a factor better than O(log n), unless P = NP. Then, we show that, unless NP DTIME(2polylog(n)), we cannot find any 2log1 ϵ n-approximation algorithm for MAL, even when a is a fixed value greater or equal to 3 and ϵ (0, 1). These results advance our knowledge on the computational complexity of MAL in two directions. |
| Researcher Affiliation | Academia | 1Gran Sasso Science Institute, L Aquila, Italy 2Aarhus University, Aarhus, Denmark EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper describes algorithmic steps and procedures, particularly in the 'Proof sketch of Theorem 8' section, but does not present them in a formal, structured pseudocode block or algorithm environment. |
| Open Source Code | No | The paper does not contain an explicit statement about the release of source code or a link to a code repository. |
| Open Datasets | No | The paper describes theoretical proofs and approximation algorithms for graph problems (Minimum Aged Labeling, Set Cover, MIN-REP) using constructed graph instances (e.g., 'Let (U, C) be an instance of SC. We construct a graph G = (V, E) which we will use to prove Theorem 2.'). It does not use or refer to any publicly available empirical datasets. |
| Dataset Splits | No | The paper describes theoretical proofs and approximation algorithms for graph problems and does not involve empirical evaluation on datasets, hence dataset splits are not applicable. |
| Hardware Specification | No | The paper presents theoretical complexity results and approximation algorithms; it does not describe any experimental evaluation requiring specific hardware. |
| Software Dependencies | No | The paper focuses on theoretical complexity and algorithm design, not experimental implementation, so no software dependencies are mentioned. |
| Experiment Setup | No | The paper is theoretical, focusing on complexity and approximation algorithms, and does not include any experimental setup details or hyperparameters. |