Fetching the paper…
Reading the bibliography…
In this paper, we provide the first deterministic algorithm that achieves the tight $1-1/e$ approximation guarantee for submodular maximization under a cardinality (size) constraint while making a number of queries that scales only linearly with the size of the ground set $n$.
Probability inequalities for sums of bounded random variables
Wassily Hoeffding · 1963
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions–II
Marshall L. Fisher, George L. Nemhauser, and Laurence A. Wolsey · 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
Vasek Chvátal · 1979
Earlier work this paper cites.
Submodular functions and optimization , volume 58
Satoru Fujishige · 1991
Earlier work this paper cites.
Fast sparse Gaussian process methods: The informative vector machine
Ralf Herbrich, Neil D Lawrence, and Matthias Seeger · 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.
Data streams: Algorithms and applications
Shanmugavelayutham Muthukrishnan · 2005
Earlier work this paper cites.
Practical budgeted submodular maximization
Moran Feldman, Zeev Nutov, and Elad Shoham · 2007
Earlier work this paper cites.
Cost-effective outbreak detection in networks
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance · 2007
Earlier work this paper cites.
Quick streaming algorithms for maximization of monotone submodular functions in linear time
Alan Kuhnle · 2009
Earlier work this paper cites.
Structured sparsity-inducing norms through submodular functions
Francis R Bach · 2010
Earlier work this paper cites.
Interactive Submodular Set Cover
Andrew Guillory and Jeff Bilmes · 2010
Earlier work this paper cites.
Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
Abhimanyu Das and David Kempe · 2011
Earlier work this paper cites.
Vsumm: A mechanism designed to produce static video summaries and a novel evaluation method
Sandra Eliza Fontes De Avila, Ana Paula Brandão Lopes, Antonio da Luz Jr, and Arnaldo de Albuquerque Araújo · 2011
Earlier work this paper cites.
Maximizing non-monotone submodular functions
Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák · 2011
Earlier work this paper cites.
Adaptive submodularity: Theory and applications in active learning and stochastic optimization
Daniel Golovin and Andreas Krause · 2011
Earlier work this paper cites.
Submodularity beyond submodular energies: coupling edges in graph cuts
Stefanie Jegelka and Jeff Bilmes · 2011
Earlier work this paper cites.
On the size of dissociated bases
Vsevolod F. Lev and Raphael Yuster · 2011
Earlier work this paper cites.
A class of submodular functions for document summarization
Hui Lin and Jeff Bilmes · 2011
Earlier work this paper cites.
Submodular Function Maximization
Andreas Krause and Daniel Golovin · 2012
Earlier work this paper cites.
Hypergeometric tail inequalities: ending the insanity
Matthew Skala · 2013
Cited alongside, same era.
Fast algorithms for maximizing submodular functions
Ashwinkumar Badanidiyuru and Jan Vondrák · 2014
Cited alongside, same era.
Streaming submodular maximization: massive data summarization on the fly
Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause · 2014
Cited alongside, same era.
SNAP Datasets: Stanford Large Network Dataset Collection
Jure Leskovec and Andrej Krevl · 2014
Cited alongside, same era.
Learning mixtures of submodular functions for image collection summarization
Sebastian Tschiatschek, Rishabh K Iyer, Haochen Wei, and Jeff A Bilmes · 2014
Cited alongside, same era.
Fast multi-stage submodular maximization
Kai Wei, Rishabh Iyer, and Jeff Bilmes · 2014
A nearly-linear time algorithm for submodular maximization with a knapsack constraint
Alina Ene and Huy L. Nguyen · 2019
Later among the works it cites.
Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity
Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi · 2019
Later among the works it cites.
Adaptive sequence submodularity
Marko Mitrovic, Ehsan Kazemi, Moran Feldman, Andreas Krause, and Amin Karbasi · 2019
Later among the works it cites.
Optimal streaming algorithms for submodular maximization with cardinality constraints
Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh · 2020
Closest in time.
Submodular Maximization Through Barrier Functions
Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi, and Jan Vondrák · 2020
Closest in time.
Streaming submodular maximization under a k-set system constraint
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
A tight linear time (1/2)-approximation for unconstrained submodular maximization
Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz · 2015
Cited alongside, same era.
The movielens datasets: History and context
F Maxwell Harper and Joseph A Konstan · 2015
Cited alongside, same era.
Sparse and greedy: Sparsifying submodular facility location problems
Erik M Lindgren, Shanshan Wu, and Alexandros G Dimakis · 2015
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.
L. Elisa Celis, Amit Deshpande, Tarun Kathuria, and Nisheeth K. Vishnoi · 2016
Cited alongside, same era.
Deep Residual Learning for Image Recognition
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun · 2016
Cited alongside, same era.
Ran Haba, Ehsan Kazemi, Moran Feldman, and Amin Karbasi · 2020
Closest in time.
Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida · 2020
Closest in time.
A note on monotone submodular maximization with cardinality constraint
Wenxin Li · 2020
Closest in time.
Coresets for data-efficient training of machine learning models
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec · 2020
Closest in time.
Submodularity in action: From machine learning to signal processing applications
Ehsan Tohidi, Rouhollah Amiri, Mario Coutino, David Gesbert, Geert Leus, and Amin Karbasi · 2020
Closest in time.
”bring your own greedy”+max: Near-optimal 1/2-approximations for submodular knapsack
Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin · 2020
Closest in time.
Adaptivity in adaptive submodularity
Hossein Esfandiari, Amin Karbasi, and Vahab Mirrokni · 2021
Closest in time.
The power of subsampling in submodular maximization
Christopher Harshaw, Ehsan Kazemi, Moran Feldman, and Amin Karbasi · 2021
Closest in time.
Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
Chien-Chung Huang and Naonori Kakimura · 2021
Closest in time.
Regularized submodular maximization at scale
Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi · 2021
Closest in time.
Quick streaming algorithms for maximization of monotone submodular functions in linear time
Alan Kuhnle · 2021
Closest in time.
A faster tight approximation for submodular maximization subject to a knapsack constraint
Ariel Kulik, Roy Schwartz, and Hadas Shachnai · 2021
Closest in time.
Near-optimal multi-perturbation experimental design for causal structure learning
Scott Sussex, Caroline Uhler, and Andreas Krause · 2021
Closest in time.
Revisiting modified greedy algorithm for monotone submodular maximization with a knapsack constraint
Jing Tang, Xueyan Tang, Andrew Lim, Kai Han, Chongshou Li, and Junsong Yuan · 2021
Closest in time.
Submodularity in machine learning and artificial intelligence
Jeff Bilmes · 2022
Closest in time.
Multi-pass streaming algorithms for monotone submodular function maximization
Chien-Chung Huang and Naonori Kakimura · 2022
Closest in time.
Personal communication, 2022
Alan Kuhnle · 2022
Closest in time.