Fetching the paper…
Reading the bibliography…
Monotone submodular maximization with a knapsack constraint is NP-hard.
Submodularity Beyond Submodular Energies: Coupling Edges in Graph Cuts. In Proc. IEEE CVPR . 1897–1904
Stefanie Jegelka and Jeff Bilmes. 2011 · 1904
Earlier work this paper cites.
Submodularity in Data Subset Selection and Active Learning. In Proc. ICML . 1954–1963
Kai Wei, Rishabh Iyer, and Jeff Bilmes. 2015 · 1963
Earlier work this paper cites.
Time Bounds for Selection
Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. 1973 · 1973
Earlier work this paper cites.
Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
Gerard Cornuejols, Marshall L Fisher, and George L Nemhauser. 1977 · 1977
Earlier work this paper cites.
Best Algorithms for Approximating the Maximum of a Submodular Set Function
George L. Nemhauser and Laurence A. Wolsey. 1978 · 1978
Earlier work this paper cites.
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.
Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
Laurence A. Wolsey. 1982 · 1982
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.
Maximum Entropy Sampling
Michael C Shewry and Henry P Wynn. 1987 · 1987
Earlier work this paper cites.
An Exact Algorithm for Maximum Entropy Sampling
Chun-Wa Ko, Jon Lee, and Maurice Queyranne. 1995 · 1995
Earlier work this paper cites.
A Threshold of ln n \ln n for Approximating Set Cover
Uriel Feige. 1998 · 1998
Earlier work this paper cites.
An 0.828-Approximation Algorithm For the Uncapacitated Facility Location Problem
Alexander A. Ageev and Maxim I. Sviridenko. 1999 · 1999
Earlier work this paper cites.
The Data-Correcting Algorithm for the Minimization of Supermodular Functions
Boris Goldengorin, Gerard Sierksma, Gert A. Tijssen, and Michael Tso. 1999 · 1999
Earlier work this paper cites.
The Budgeted Maximum Coverage Problem
Samir Khuller, Anna Moss, and Joseph Naor. 1999 · 1999
Earlier work this paper cites.
Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images. In Proc. IEEE ICCV , Vol. 1. 105–112
Yuri Y Boykov and Marie-Pierre Jolly. 2001 · 2001
Earlier work this paper cites.
Maximizing the Spread of Influence Through a Social Network. In Proc. ACM KDD . 137–146
David Kempe, Jon Kleinberg, and Éva Tardos. 2003 · 2003
Cited alongside, same era.
A Note on Maximizing a Submodular Set Function Subject to a Knapsack Constraint
Maxim Sviridenko. 2004 · 2004
Cited alongside, same era.
Influential Nodes in a Diffusion Model for Social Networks. In Proc. ICALP . 1127–1138
David Kempe, Jon Kleinberg, and Éva Tardos. 2005 · 2005
Cited alongside, same era.
Near-Optimal Nonmyopic Value of Information in Graphical Models. In Proc. UAI . 324–331
Andreas Krause and Carlos Guestrin. 2005 · 2005
Cited alongside, same era.
Near-Optimal Observation Selection using Submodular Functions. In Proc. AAAI . 1650–1654
Andreas Krause and Carlos Guestrin. 2007 · 2007
Cited alongside, same era.
Cost-effective Outbreak Detection in Networks. In Proc. ACM KDD . 420–429
SNAP Datasets: Stanford Large Network Dataset Collection
Jure Leskovec and Andrej Krevl. 2014 · 2014
Later among the works it cites.
Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations. In Proc. AAAI . 138–144
Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. 2014 · 2014
Later among the works it cites.
Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature. In Proc. SODA . 1134–1148
Maxim Sviridenko, Jan Vondrák, and Justin Ward. 2015 · 2015
Later among the works it cites.
Profit Maximization for Viral Marketing in Online Social Networks. In Proc. IEEE ICNP . 1–10
Jing Tang, Xueyan Tang, and Junsong Yuan. 2016 · 2016
Later among the works it cites.
Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
Yuichi Yoshida. 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…
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. 2007 · 2007
Cited alongside, same era.
Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks
Andreas Krause, Jure Leskovec, Carlos Guestrin, Jeanne Vanbriesen, and Christos Faloutsos. 2008a · 2008
Cited alongside, same era.
Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies
Andreas Krause, Ajit Singh, and Carlos Guestrin. 2008b · 2008
Cited alongside, same era.
What is Twitter, a Social Network or a News Media?. In Proc. WWW . 591–600
Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010 · 2010
Cited alongside, same era.
Multi-Document Summarization via Budgeted Maximization of Submodular Functions. In Proc. NAACL-HLT . 912–920
Hui Lin and Jeff Bilmes. 2010 · 2010
Cited alongside, same era.
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. 2011 · 2011
Cited alongside, same era.
A Class of Submodular Functions for Document Summarization. In Proc. HLT . 510–520
Hui Lin and Jeff Bilmes. 2011 · 2011
Cited alongside, same era.
Submodular Asymmetric Feature Selection in Cascade Object Detection. In Proc. AAAI . 1387–1393
Baosheng Yu, Meng Fang, Dacheng Tao, and Jie Yin. 2016 · 2016
Later among the works it cites.
Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach. In Proc. IEEE/ACM ASONAM . 64–71
Jing Tang, Xueyan Tang, and Junsong Yuan. 2017 · 2017
Later among the works it cites.
Efficient Algorithms for Adaptive Influence Maximization
Kai Han, Keke Huang, Xiaokui Xiao, Jing Tang, Aixin Sun, and Xueyan Tang. 2018 · 2018
Later among the works it cites.
An Efficient and Effective Hop-Based Approach for Inluence Maximization in Social Networks
Jing Tang, Xueyan Tang, and Junsong Yuan. 2018a · 2018
Later among the works it cites.
Profit Maximization for Viral Marketing in Online Social Networks: Algorithms and Analysis
Jing Tang, Xueyan Tang, and Junsong Yuan. 2018b · 2018
Later among the works it cites.
Trajectory-driven Influential Billboard Placement. In Proc. ACM KDD . 2748–2757
Ping Zhang, Zhifeng Bao, Yuchen Li, Guoliang Li, Yipeng Zhang, and Zhiyong Peng. 2018 · 2018
Later among the works it cites.
A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. In Proc. ICALP . 53:1–53:12
Alina Ene and Huy L. Nguyen. 2019 · 2019
Later among the works it cites.
Efficient Approximation Algorithms for Adaptive Seed Minimization. In Proc. ACM SIGMOD . 1096–1113
Jing Tang, Keke Huang, Xiaokui Xiao, Laks V.S. Lakshmanan, Xueyan Tang, Aixin Sun, and Andrew Lim. 2019 · 2019
Later among the works it cites.
Efficient Approximation Algorithms for Adaptive Influence Maximization
Keke Huang, Jing Tang, Kai Han, Xiaokui Xiao, Wei Chen, Aixin Sun, Xueyan Tang, and Andrew Lim. 2020a · 2020
Closest in time.