Fetching the paper…
Reading the bibliography…
While greedy algorithms have long been observed to perform well on a wide variety of problems, up to now approximation ratios have only been known for their application to problems having submodular objective functions $f$.
An Analysis of Approximations for Maximizing Submodular Set functions – I
George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. 1978 · 1978
Earlier work this paper cites.
Submodular Set Functions, Matroids and the Greedy Algorithm: Tight Worst-Case Bounds and Some Generalizations of the Rado-Edmonds Theorem
Michele Conforti and Gérard Cornuéjols. 1984 · 1984
Earlier work this paper cites.
Matroid theory
James G. Oxley. 1992 · 1992
Earlier work this paper cites.
Maximizing the Spread of Influence Through a Social Network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
David Kempe, Jon Kleinberg, and Éva Tardos · 2003
Earlier work this paper cites.
Cost-Effective Outbreak Detection in Networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance · 2007
Earlier work this paper cites.
Submodularity and curvature: the optimal algorithm
Jan Vondrák. 2010 · 2010
Earlier work this paper cites.
The Socialbot Network: When Bots Socialize for Fame and Money. In Proceedings of the 27th Annual Computer Security Applications Conference
Yazan Boshmaf, Ildar Muslukhov, Konstantin Beznosov, and Matei Ripeanu · 2011
Earlier work this paper cites.
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
Daniel Golovin and Andreas Krause. 2011 · 2011
Cited alongside, same era.
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)
N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz · 2012
Cited alongside, same era.
Adaptive Seeding in Social Networks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science
L. Seeman and Y. Singer · 2013
Cited alongside, same era.
Maximizing Social Influence in Nearly Optimal Time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier · 2014
Cited alongside, same era.
Approximation for maximizing monotone non-decreasing set functions with a greedy method
Zengfu Wang, Bill Moran, Xuezhi Wang, and Quan Pan. 2014 · 2014
Robust Influence Maximization. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Xinran He and David Kempe. 2016 · 2016
Later among the works it cites.
Privacy Issues in Light of Reconnaissance Attacks with Incomplete Information. In Proceedings of the 2016 IEEE/WIC/ACM International Conference on Web Intelligence
Xiang Li, J. David Smith, Thang N. Dinh, and My T. Thai. 2016 · 2016
Later among the works it cites.
Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-Scale Networks. In Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data
Hung T. Nguyen, Thang N. Dinh, and My T. Thai · 2016
Later among the works it cites.
String Submodular Functions With Curvature Constraints
Z. Zhang, E. K. P. Chong, A. Pezeshki, and W. Moran. 2016 · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms
Maxim Sviridenko, Jan Vondrák, and Justin Ward · 2015
Cited alongside, same era.
Influence Maximization in Near-Linear Time: A Martingale Approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data
Youze Tang, Yanchen Shi, and Xiaokui Xiao · 2015
Cited alongside, same era.
An Analysis of Approximations for Maximizing Submodular Set functions—II
Marshall L. Fisher, George L. Nemhauser, and Laurence A. Wolsey
Cited in the paper.
Near-Optimal Bayesian Active Learning with Noisy Observations
Daniel Golovin, Andreas Krause, and Debajyoti Ray
Cited in the paper.
Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
Jon Lee, Maxim Sviridenko, and Jan Vondrák
Cited in the paper.
Xiang Li, J. David Smith, Thang N. Dinh, and My T. Thai. 2017 · 2017
Closest in time.
Distributed Submodular Maximization: Identifying Representative Elements in Massive Data
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause · 2057
Closest in time.