Efficient Approximation Algorithms for Adaptive Seed Minimization

Summary: Adaptive seed minimization in social networks with batchwise feedback; ASTI exploits observed diffusion in rounds to reduce seeds. Offers (1 - (1 - 1/b)^b)(1 - 1/e)(1 - ε) approximation in expectation in O((η(m+n))/ε^2 ln n) time; first scalable adaptive guarantee, supported by experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5694
Venue: SIGMOD
Year: 2019
Pagerank: 5.1641945e-05
Overall Rank: 6,181 | 57.05%
DOI: 10.1145/3299869.3319881

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,668	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD	8.3432296e-05
5,170	Pricing Influential Nodes in Online Social Networks	2020	VLDB	5.6416844e-05
8,007	Analysis of Influence Contribution in Social Advertising	2022	VLDB	4.604154e-05
8,737	Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee	2024	SIGMOD	4.4520434e-05
8,808	Efficient and Effective Algorithms for Revenue Maximization in Social Advertising	2021	SIGMOD	4.4413146e-05
9,712	Unconstrained Submodular Maximization with Modular Costs: Tight Approximation and Application to Profit Maximization	2021	VLDB	4.2951473e-05
10,206	Robust Fair Influence Maximization under Multiple Community Partitions	2026	SIGMOD	4.1905499e-05
11,210	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
90	A Data-Based Approach to Social Influence Maximization	2012	VLDB	0.00052018478
180	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD	0.00037101192
338	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00026987013
437	Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks	2016	SIGMOD	0.00023237348
1,652	Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study	2017	SIGMOD	0.00010999442
1,798	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010500792
2,226	Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models	2016	SIGMOD	9.2532857e-05
4,219	Revisiting the Stop-and-Stare Algorithms for Influence Maximization	2017	VLDB	6.3432726e-05
5,092	Efficient Algorithms for Adaptive Influence Maximization	2018	VLDB	5.6987819e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,546	Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint	2025	VLDB	4.1905499e-05
5,077	Efficient Location-Aware Influence Maximization	2014	SIGMOD	5.7098565e-05
4,369	Real-Time Influence Maximization on Dynamic Social Streams	2017	VLDB	6.2399378e-05
11,210	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD	4.1905499e-05
2,490	Online Topic-Aware Influence Maximization	2015	VLDB	8.6500989e-05
338	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00026987013
8,904	Efficient Influence Minimization via Node Blocking	2024	VLDB	4.4229886e-05
8,737	Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee	2024	SIGMOD	4.4520434e-05
2,485	Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks	2020	VLDB	8.6657901e-05
5,092	Efficient Algorithms for Adaptive Influence Maximization	2018	VLDB	5.6987819e-05