Fetching the paper…
Reading the bibliography…
We present a simple combinatorial $\frac{1 -e^{-2}}{2}$-approximation algorithm for maximizing a monotone submodular function subject to a knapsack and a matroid constraint.
An analysis of approximations for maximizing submodular set functions—ii
M. Fisher, G. Nemhauser, and L. Wolsey · 1978
Earlier work this paper cites.
Best algorithms for approximating the maximum of submodular set function
G. Nemhauser and L. Wolsey · 1978
Earlier work this paper cites.
An analysis of the approximations for maximizing submodular set functions - i
G. Nemhauser, L. Wolsey, and M. Fisher · 1978
Earlier work this paper cites.
Maximizing real-valued submodular functions: Primal and dual heuristics for location problems
L. A. Wolsey · 1982
Earlier work this paper cites.
A threshold of ln n \ln n for approximating set cover
Uriel Feige · 1998
Earlier work this paper cites.
The budgeted maximum coverage problem
Samir Khuller, Anna Moss, and Joseph (Seffi) Naor · 1999
Earlier work this paper cites.
Introduction to algorithms
Thomas H. Cormen, Charles Eric Leiserson, Ronald L Rivest, and Clifford Stein · 2001
Earlier work this paper cites.
Maximizing the spread of influence through a social network
David Kempe, Jon M. Kleinberg, and Éva Tardos · 2003
Earlier work this paper cites.
A note on maximizing a submodular set function subject to knapsack constraint
M. Sviridenko · 2004
Earlier work this paper cites.
Influential nodes in a diffusion model for social networks
David Kempe, Jon M. Kleinberg, and Éva Tardos · 2005
Earlier work this paper cites.
An improved approximation algorithm for combinatorial auctions with submodular bidders
Shahar Dobzinski and Michael Schapira · 2006
Earlier work this paper cites.
On the complexity of approximating k -set packing
Elad Hazan, Shmuel Safra, and Oded Schwartz · 2006
Earlier work this paper cites.
Maximizing non-monotone submodular functions
Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák · 2007
Cited alongside, same era.
Optimal approximation for the submodular welfare problem in the value oracle model
Jan Vondrák · 2008
Cited alongside, same era.
Dependent randomized rounding via exchange properties of combinatorial structures
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen · 2010
Cited alongside, same era.
Thresholded covering algorithms for robust and max-min optimization
Anupam Gupta, Viswanath Nagarajan, and R. Ravi · 2010
Cited alongside, same era.
Constrained non-monotone submodular maximization: Offline and secretary algorithms
Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar · 2010
Cited alongside, same era.
Constrained non-monotone submodular maximization: Offline and secretary algorithms
A tight combinatorial algorithm for submodular maximization subject to a matroid constraint
Yuval Filmus and Justin Ward · 2012
Later among the works it cites.
Temporal corpus summarization using submodular word coverage
Ruben Sipos, Adith Swaminathan, Pannaga Shivaswamy, and Thorsten Joachims · 2012
Later among the works it cites.
Maximization Problems with Submodular Objective Functions
Moran Feldman · 2013
Later among the works it cites.
Approximations for monotone and nonmonotone submodular maximization with knapsack constraints
Ariel Kulik, Hadas Shachnai, and Tami Tamir · 2013
Later among the works it cites.
Fast algorithms for maximizing submodular functions
Ashwinkumar Badanidiyuru and Jan Vondrák · 2014
Later among the works it cites.
Submodular function maximization via the multilinear relaxation and contention resolution schemes
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar · 2010
Cited alongside, same era.
Maximizing nonmonotone submodular functions under matroid or knapsack constraints
Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko · 2010
Cited alongside, same era.
Matroid matching: the power of local search
Jon Lee, Maxim Sviridenko, and Jan Vondrák · 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
Cited alongside, same era.
Nonmonotone submodular maximization via a structural continuous greedy algorithm - (extended abstract)
Moran Feldman, Joseph Naor, and Roy Schwartz · 2011
Cited alongside, same era.
A unified continuous greedy algorithm for submodular maximization
Moran Feldman, Joseph Naor, and Roy Schwartz · 2011
Cited alongside, same era.
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen · 2014
Later among the works it cites.
Submodularity for data selection in machine translation
Katrin Kirchhoff and Jeff A. Bilmes · 2014
Later among the works it cites.
A tight linear time (1/2)-approximation for unconstrained submodular maximization
Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz · 2015
Later among the works it cites.
All-or-nothing generalized assignment with application to scheduling advertising campaigns
Ron Adany, Moran Feldman, Elad Haramaty, Rohit Khandekar, Baruch Schieber, Roy Schwartz, Hadas Shachnai, and Tami Tamir · 2016
Later among the works it cites.
Robust and maxmin optimization under matroid and knapsack uncertainty sets
Anupam Gupta, Viswanath Nagarajan, and R Ravi · 2016
Later among the works it cites.
Greed is good: Near-optimal submodular maximization via greedy optimization
Moran Feldman, Christopher Harshaw, and Amin Karbasi · 2017
Closest in time.