Balancing Spreads of Influence in a Social Network
Authors: Ruben Becker, Federico Corò, Gianlorenzo D'Angelo, Hugo Gilbert44995
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | While for the simplified setting, we show that the problem can be approximated within a constant factor for any constant μ and ν, for the general setting, we give reductions leading to several approximation hardness results when ν 3. For instance, assuming the gap exponential time hypothesis to hold, we obtain that the problem cannot be approximated within a factor of n g(n) for any g(n) = o(1) where n is the number of nodes in the network. We complement our hardness results with an Ω(n 1/2)-approximation algorithm for the general setting when ν = 3 and μ is arbitrary. |
| Researcher Affiliation | Academia | Ruben Becker, Federico Cor o, Gianlorenzo D Angelo, Hugo Gilbert Gran Sasso Science Institute, L Aquila Italy |
| Pseudocode | Yes | Algorithm 1: GREEDYTUPLE(ϵ, δ, ℓ, I, ν, k); Algorithm 2: GREEDYITER(ϵ, δ, I, ν, k) |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code or a link to a code repository. |
| Open Datasets | No | The paper is theoretical, focusing on algorithm design and approximation guarantees for a problem defined on a graph G=(V,E). It does not describe experiments using datasets, and therefore no training, validation, or test data splits are mentioned. |
| Dataset Splits | No | The paper is theoretical, focusing on algorithm design and approximation guarantees for a problem defined on a graph G=(V,E). It does not describe experiments using datasets, and therefore no training, validation, or test data splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and complexity analysis. It does not describe any computational experiments or the hardware used to run them. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and complexity analysis. It does not mention any specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and does not include details on an experimental setup such as hyperparameters or training configurations. |