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: 5693
Venue: SIGMOD
Year: 2019
Pagerank: 5.1691599e-05
Overall Rank: 6,179 | 57.02%
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,664	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD	8.3512717e-05
5,170	Pricing Influential Nodes in Online Social Networks	2020	VLDB	5.6471109e-05
8,003	Analysis of Influence Contribution in Social Advertising	2022	VLDB	4.6085729e-05
8,741	Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee	2024	SIGMOD	4.456315e-05
8,807	Efficient and Effective Algorithms for Revenue Maximization in Social Advertising	2021	SIGMOD	4.4455759e-05
9,713	Unconstrained Submodular Maximization with Modular Costs: Tight Approximation and Application to Profit Maximization	2021	VLDB	4.299267e-05
10,206	Robust Fair Influence Maximization under Multiple Community Partitions	2026	SIGMOD	4.1945683e-05
11,208	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD	4.1945683e-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.00052068982
180	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD	0.00037135181
337	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00027011645
436	Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks	2016	SIGMOD	0.00023259324
1,652	Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study	2017	SIGMOD	0.00011010086
1,801	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010510943
2,220	Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models	2016	SIGMOD	9.2622402e-05
4,220	Revisiting the Stop-and-Stare Algorithms for Influence Maximization	2017	VLDB	6.3493792e-05
5,090	Efficient Algorithms for Adaptive Influence Maximization	2018	VLDB	5.7042676e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,537	Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint	2025	VLDB	4.1945683e-05
5,078	Efficient Location-Aware Influence Maximization	2014	SIGMOD	5.715243e-05
4,371	Real-Time Influence Maximization on Dynamic Social Streams	2017	VLDB	6.2459569e-05
11,208	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD	4.1945683e-05
2,490	Online Topic-Aware Influence Maximization	2015	VLDB	8.6584707e-05
337	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00027011645
8,903	Efficient Influence Minimization via Node Blocking	2024	VLDB	4.427232e-05
8,741	Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee	2024	SIGMOD	4.456315e-05
2,486	Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks	2020	VLDB	8.6741469e-05
5,090	Efficient Algorithms for Adaptive Influence Maximization	2018	VLDB	5.7042676e-05