Skip to content
Book Open access

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

Aug 2026 · Knowledge Discovery and Data Mining · pp. 1108-1119 · 0 citations · 46 references
Computer Science

TL;DR

The EMASS framework, which achieves an approximation ratio of (ln η+1)2/[(1-1/e)2-ε], where ε is the estimation error of mRR-sets, is proposed, which eliminates the need to regenerate mRR-sets in each round and thus the computation overhead is reduced significantly.

Abstract

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. In this paper, we attempt to solve AMCS under general user costs with high efficiency. To this end, we propose the EMASS framework which achieves an approximation ratio of (ln η+1)2/[(1-1/e)2-ε], where ε is the estimation error of mRR-sets. To generate mRR-sets efficiently, we develop a series of algorithms to update mRR-sets across rounds, which support the generation, root insertion, and cleaning of mRR-sets. In this way, we eliminate the need to regenerate mRR-sets in each round and thus the computation overhead is reduced significantly. Further, we prove that the updated mRR-sets are equal to the regenerated ones. Finally, extensive experiments on real social networks demonstrate that EMASS is faster than state-of-the-art methods by over an order of magnitude, while the influence target η is always reached with the total user cost among the lowest.

Read PDF

Similar papers

Sep 2026

Budget-Independent Influence Maximization in Nearly Linear Time

This work reserves $O(\varepsilon k)$ seed positions for cost-weighted random vertices, allowing reverse-reachable searches to stop as soon as they encounter a reserved seed.

Zhi-Jie Zhang · 1 citation
Preprint Nov 2026

Approximation Algorithms for Multi-Criteria Network Design Problems

It is shown that exponentially better and nearly optimal guarantees are achievable for two fundamental network design problems: Min-max multi-criteria optimization and multi-criteria connectivity augmentation.

Mehrshad Taziki, A. Vakilian · 0 citations
Nov 2026

Dynamic Non-Submodular Maximization Over Cardinality and Matroid Constraints

Dynamic submodular maximization tackles the challenge of maintaining approximate solutions for evolving datasets, where elements are inserted or deleted over time. Unlike static or streaming models, this setting requires efficiently updating the solution after each data modification without reprocessing the entire data...

Xin Sun, Xin-Hui Si · 0 citations

Dual-GNN Multilevel Coarsening for Maximum Independent Set

The Dual-GNN Multilevel Coarsening framework uses learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making and achieves the best mean solution quality among all evaluated methods.

Tian-Feng Chen, Xian-Yue Li · 0 citations
Preprint Oct 2026

A Link-Based Algorithm for Stochastic User Equilibrium with Bounded Choice and Local Detour Threshold

This study develops a novel solution method for stochastic user equilibrium (SUE) under the bounded choice model with local detour threshold (BCM-LDT SUE; Rasmussen et al., 2024), which restricts the choice set in line with observed route choice behavior. The model assigns zero probability to paths whose total cost exc...

Takeshi Nagae · 0 citations
Sep 2026

A Robustified Greedy Algorithm for Online Transportation with Improved Competitive Guarantees

We study the \emph{online transportation problem}, in which $n$ requests arriving sequentially in a metric space must be irrevocably assigned to $k$ capacitated facilities. Beyond classical logistics applications, this problem models resource-allocation tasks arising in machine learning, including online facility assig...

Ritesh Seth, Syamantak Das, S. Raghvendra · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.