Efficient Approximation Algorithms for Adaptive Minimum Cost Seed Selection via mRR-set Updates

In a social network G with user costs c(•), the adaptive minimum cost seed selection (AMCS) problem aims to influence at least η users at minimum total cost, where seed users are selected iteratively based on observed diffusion. Prior work shows that truncating user influence by η is necessary for performance guarantees, and proposes multi-root reverse reachable sets (mRR-sets) to estimate truncated influence. However, to maintain estimation accuracy, all mRR-sets must be regenerated in each round to exclude influenced users, which limits scalability. Moreover, existing methods assume uniform user costs, inconsistent with practical scenarios.