Fetching the paper…
Reading the bibliography…
It is generally believed that submodular functions -- and the more general class of $\gamma$-weakly submodular functions -- may only be optimized under the non-negativity assumption $f(S) \geq 0$.
Probability inequalities for sums of bounded random variables
Wassily Hoeffding · 1963
Earlier work this paper cites.
Hedonic housing prices and the demand for clean air
David Harrison Jr. and Daniel L Rubenfield · 1978
Earlier work this paper cites.
Accelerated greedy algorithms for maximizing submodular set functions
Michel Minoux · 1978
Earlier work this paper cites.
Best algorithms for approximating the maximum of a submodular set function
G L Nemhauser and L A Wolsey · 1978
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions–I
G L Nemhauser, L A Wolsey, and M L Fisher · 1978
Earlier work this paper cites.
The tail of the hypergeometric distribution
V. Chvátal · 1979
Earlier work this paper cites.
Fast approximate energy minimization via graph cuts
Y. Boykov, O. Veksler, and R. Zabih · 2001
Earlier work this paper cites.
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, and Éva Tardos · 2003
Earlier work this paper cites.
A note on maximizing a submodular set function subject to a knapsack constraint
Maxim Sviridenko · 2004
Earlier work this paper cites.
Near-optimal Nonmyopic Value of Information in Graphical Models
A. Krause and C. Guestrin · 2005
Earlier work this paper cites.
Graph evolution: Densification and shrinking diameters
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos · 2007
Earlier work this paper cites.
Submodular maximization over multiple matroids via generalized exchange properties
Jon Lee, Maxim Sviridenko, and Jan Vondrák · 2010
Cited alongside, same era.
Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
Abhimanyu Das and David Kempe · 2011
Cited alongside, same era.
Adaptive submodularity: Theory and applications in active learning and stochastic optimization
Daniel Golovin and Andreas Krause · 2011
Cited alongside, same era.
Submodularity beyond submodular energies: coupling edges in graph cuts
Stefanie Jegelka and Jeff Bilmes · 2011
Cited alongside, same era.
A class of submodular functions for document summarization
Hui Lin and Jeff Bilmes · 2011
Cited alongside, same era.
Efficient feature group sequencing for anytime linear prediction
Hanzhang Hu, Alexander Grubb, J. Andrew Bagnell, and Martial Hebert · 2016
Later among the works it cites.
Guarantees for greedy maximization of non-submodular functions with applications
Andrew An Bian, Joachim M. Buhmann, Andreas Krause, and Sebastian Tschiatschek · 2017
Later among the works it cites.
Approximate supermodularity bounds for experimental design
Luiz F. O. Chamon and Alejandro Ribeiro · 2017
Later among the works it cites.
Streaming weak submodularity: Interpreting neural networks on the fly
Ethan R. Elenberg, Alexandros G. Dimakis, Moran Feldman, and Amin Karbasi · 2017
Later among the works it cites.
Greed is good: Near-optimal submodular maximization via greedy optimization
Moran Feldman, Christopher Harshaw, and Amin Karbasi · 2017
Later among the works it cites.
Scalable Greedy Feature Selection via Weak Submodularity
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Matthew Skala · 2013
Cited alongside, same era.
Using Document Summarization Techniques for Speech Data Subset Selection
Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes · 2013
Cited alongside, same era.
Submodular function maximization via the multilinear relaxation and contention resolution schemes
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen · 2014
Cited alongside, same era.
Lazier than lazy greedy
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause · 2015
Cited alongside, same era.
Constrained submodular maximization via a non-symmetric technique
Niv Buchbinder and Moran Feldman · 2016
Cited alongside, same era.
Constrained submodular maximization: Beyond 1/e
Alina Ene and Huy L. Nguyen · 2016
Cited alongside, same era.
Rajiv Khanna, Ethan R. Elenberg, Alexandros G. Dimakis, Sahand Negahban, and Joydeep Ghosh · 2017
Later among the works it cites.
Optimal approximation for submodular and supermodular optimization with bounded curvature
Maxim Sviridenko, Jan Vondrák, and Justin Ward · 2017
Later among the works it cites.
Local higher-order graph clustering
Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich · 2017
Later among the works it cites.
Restricted strong convexity implies weak submodularity
Ethan R. Elenberg, Rajiv Khanna, Alexandros G. Dimakis, and Sahand Negahban · 2018
Later among the works it cites.
Fast maximization of non-submodular, monotonic functions on the integer lattice
Alan Kuhnle, J. David Smith, Victoria G. Crawford, and My T. Thai · 2018
Later among the works it cites.
Guess free maximization of submodular and linear sums, 2019
Moran Feldman · 2019
Closest in time.