Fetching the paper…
Reading the bibliography…
We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models.
Best algorithms for approximating the maximum of a submodular set function
George L. Nemhauser and Laurence A. Wolsey · 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
Earlier work this paper cites.
A threshold of ln n \ln n for approximating set cover
Uriel Feige · 1998
Earlier work this paper cites.
Information theory methods in communication complexity
Ziv Bar-Yossef, Thathachar S. Jayram, Ravi Kumar, and D. Sivakumar · 2002
Earlier work this paper cites.
Combinatorial Optimization - Polyhedra and Efficiency
A. Schrijver · 2003
Earlier work this paper cites.
Lower bounds for multi-player pointer jumping
A. Chakrabarti · 2007
Earlier work this paper cites.
The one-way communication complexity of hamming distance
Thathachar S Jayram, Ravi Kumar, and D Sivakumar · 2008
Earlier work this paper cites.
Structured sparsity-inducing norms through submodular functions
Francis R. Bach · 2010
Earlier work this paper cites.
Maximizing a monotone submodular function subject to a matroid constraint
Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák · 2011
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.
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.
Selecting diverse features via spectral regularization
Abhimanyu Das, Anirban Dasgupta, and Ravi Kumar · 2012
Earlier work this paper cites.
Better bounds for matchings in the streaming model
Michael Kapralov · 2013
Earlier work this paper cites.
Streaming submodular maximization: Massive data summarization on the fly
Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause · 2014
Earlier work this paper cites.
Submodular maximization meets streaming: Matchings, matroids, and more
Amit Chakrabarti and Sagar Kale · 2014
Cited alongside, same era.
Submodular attribute selection for action recognition in video
Jingjing Zheng, Zhuolin Jiang, Rama Chellappa, and P. Jonathon Phillips · 2014
Cited alongside, same era.
Online submodular maximization with preemption
Niv Buchbinder, Moran Feldman, and Roy Schwartz · 2015
Cited alongside, same era.
Summarization of multi-document topic hierarchies using submodular mixtures
Ramakrishna Bairi, Rishabh K. Iyer, Ganesh Ramakrishnan, and Jeff A. Bilmes · 2015
Cited alongside, same era.
The power of randomization: Distributed submodular maximization on massive datasets
Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, and Justin Ward · 2015
Cited alongside, same era.
Beyond 1/2-approximation for submodular maximization on massive data streams
Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrovic, Amir Zandieh, Aidasadat Mousavifar, and Ola Svensson · 2018
Later among the works it cites.
An exponential speedup in parallel running time for submodular maximization without loss in approximation
Eric Balkanski, Aviad Rubinstein, and Yaron Singer · 2019
Later among the works it cites.
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
Eric Balkanski, Aviad Rubinstein, and Yaron Singer · 2019
Later among the works it cites.
Unconstrained submodular maximization with constant adaptive complexity
Lin Chen, Moran Feldman, and Amin Karbasi · 2019
Later among the works it cites.
Submodular function maximization in parallel via the multilinear relaxation
Chandra Chekuri and Kent Quanrud · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Vahab S. Mirrokni and Morteza Zadimoghaddam · 2015
Cited alongside, same era.
A new framework for distributed submodular maximization
Rafael Barbosa, Alina Ene, Huy L. Nguyen, and Justin Ward · 2016
Cited alongside, same era.
Robust monotone submodular function maximization
James B. Orlin, Andreas S. Schulz, and Rajan Udwani · 2016
Cited alongside, same era.
Robust submodular maximization: A non-uniform partitioning approach
Ilija Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher · 2017
Cited alongside, same era.
Streaming robust submodular maximization: A partitioned thresholding approach
Slobodan Mitrović, Ilija Bogunovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Volkan Cevher · 2017
Cited alongside, same era.
Deletion-robust submodular maximization: Data summarization with “the right to be forgotten”
Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause · 2017
Cited alongside, same era.
Submodular secretary problem with shortlists
Shipra Agrawal, Mohammad Shadravan, and Cliff Stein · 2018
Cited alongside, same era.
Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time
Alina Ene and Huy L. Nguyen · 2019
Later among the works it cites.
Submodular maximization with matroid and packing constraints in parallel
Alina Ene, Huy L. Nguyen, and Adrian Vladu · 2019
Later among the works it cites.
Non-monotone submodular maximization with nearly optimal adaptivity and query complexity
Matthew Fahrbach, Vahab S. Mirrokni, and Morteza Zadimoghaddam · 2019
Later among the works it cites.
Submodular maximization with nearly optimal approximation, adaptivity and query complexity
Matthew Fahrbach, Vahab S. Mirrokni, and Morteza Zadimoghaddam · 2019
Later among the works it cites.
Independent sets in vertex-arrival streams
C. Konrad G. Cormode, J. Dark · 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.
Submodular optimization in the mapreduce model
Paul Liu and Jan Vondrák · 2019
Later among the works it cites.
Better streaming algorithms for the maximum coverage problem
Andrew McGregor and Hoa T. Vu · 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.
Chien-Chung Huang, Naonori Kakimura, Simon Mauras, and Yuichi Yoshida · 2020
Closest in time.