# Time-constrained Adaptive Influence Maximization

arXiv: https://arxiv.org/abs/2001.01742 · HTML: https://mlsanity.com/paper/2001.01742/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2020.

## Built on by (most cited first, 4 of 4)

- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [Many-Objective Evolutionary Influence Maximization: Balancing Spread, Budget, Fairness, and Time](https://mlsanity.com/paper/2403.18755/) (2024)
- [Stochastic Multi-round Submodular Optimization with Budget](https://mlsanity.com/paper/2404.13737/) (2024)
- [Learning Multi-Timescale Abstractions for Hierarchical Combinatorial Planning](https://mlsanity.com/paper/2605.17058/) (2026)

## Abstract (arXiv)

The well-known influence maximization problem aims at maximizing the influence of one information cascade in a social network by selecting appropriate seed users prior to the diffusion process. In its adaptive version, additional seed users can be selected after observing certain diffusion results. On the other hand, social computing tasks are often time-critical, and therefore only the influence resulted in the early period is worthwhile, which can be naturally modeled by enforcing a time constraint. In this paper, we present an analysis of the time-constrained adaptive influence maximization problem. We show that the new problem is combinatorially different from the existing problems, and the current techniques such as submodular maximization and adaptive submodularity are unfortunately inapplicable. On the theory side, we provide the hardness results of computing the optimal policy and a lower bound on the adaptive gap. For practical solutions, from basic to advanced, we design a series of seeding policies for achieving high efficacy and scalability. Finally, we investigate the proposed solutions through extensive simulations based on real-world datasets.