Adaptive Influence Maximization: Adaptability via Nonadaptability

Adaptive influence maximization is an important research problem in computational social networks, which is also a typical problem in the study of adaptive processing of information and adaptive construction of objects. In this paper, we propose a new method that reduces the adaptive influence maximization problem into a nonadaptive one in a different social network, so that an adaptive optimization can be solved by those methods for nonadaptive optimization. In addition, we provide a new approximation algorithm for the submodular maximization problem with a knapsack constraint, which runs in $O(n^2)$ time and has performance ratio $1-1/\sqrt{e}$, where n is the number of nodes in the network. The ratio is better than the best known previous one with the same running time.

History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms.

Funding: This research is supported in part by the National Natural Science Foundation of China [Grant U20A2068].