Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback
Authors: Gianlorenzo D'Angelo, Debashmita Poddar, Cosimo Vinci12069-12077
AAAI 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is the ๏ฌrst sub-linear upper bound that holds for any graph. Speci๏ฌcally, we show that the adaptivity gap is upper-bounded by 3 n+ 1, where n is the number of nodes in the graph. Moreover we improve over the known upper bound for in-arborescences from 2e/(e โ 1) โ 3.16 to 2e2/(e2 โ 1) โ 2.31. Finally, we study ฮฑ-bounded graphs, a class of undirected graphs in which the sum of node degrees higher than two is at most ฮฑ, and show that the adaptivity gap is upper-bounded by ฮฑ+ O(1). Moreover, we show that in 0-bounded graphs, i.e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most 3e3/(e3 โ 1) โ 3.16. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest. |
| Researcher Affiliation | Academia | Gianlorenzo D Angelo, Debashmita Poddar, and Cosimo Vinci Gran Sasso Science Institute, L Aquila, Italy EMAIL |
| Pseudocode | Yes | Algorithm 1 Adaptive algorithm Require: an in๏ฌuence graph ํบand an adaptive policy ํ; Ensure: a partial realisation; 1: let ํฟbe the live-edge graph; 2: let ํ:= (i.e., ํis the empty partial realisation); 3: while ํ(ํ) ํํํํdo 4: ํฃ:= ํ(ํ); 5: ํ:= ํ {(ํฃ, ํ ({ํฃ}, ํฟ))}; 6: end while 7: return ํํ,ํฟ:= ํ; |
| Open Source Code | No | The paper does not provide any concrete access information (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology's source code. |
| Open Datasets | No | This paper is theoretical and focuses on mathematical proofs and bounds for influence maximization. It does not describe experiments with datasets, thus no dataset is mentioned as publicly available or open. |
| Dataset Splits | No | This paper is theoretical and focuses on mathematical proofs and bounds. It does not describe empirical experiments with datasets, and therefore no training/validation/test dataset splits are provided. |
| Hardware Specification | No | This is a theoretical paper that focuses on mathematical proofs and algorithms. It does not describe any computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | This is a theoretical paper that focuses on mathematical proofs and algorithms. It does not describe any computational experiments that would involve specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper that focuses on mathematical proofs and algorithms. It does not describe any empirical experiments that would require an experimental setup with hyperparameters or training settings. |