Fast algorithms for maximizing submodular functions
By Ashwinkumar Badanidiyuru, Jan Vondr'ak. ACM-SIAM Symposium on Discrete Algorithms, 2014
347 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
View Paper: https://www.semanticscholar.org/paper/99ba32eb17d05f63297b1fb067a515c2a354cc7b
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Amin Karbasi
- Moran Feldman
- Baharan Mirzasoleiman
- Andreas Krause
- Ashwinkumar Badanidiyuru
- Jan Vondr'ak
- Ehsan Kazemi
- Wenxin Li
In Computational Theory and Mathematics
- Amin Karbasi
- Moran Feldman
- Andreas Krause
- Baharan Mirzasoleiman
- Ashwinkumar Badanidiyuru
- Jan Vondr'ak
- Ehsan Kazemi
- Wenxin Li
Citations in the corpus
- Lazier Than Lazy Greedy (2014, methodology): “Very recently, Badanidiyuru et al. (2014) provided the first one-pass streaming algorithm with a constant factor approximation guarantee for general submodular functions without any assumption about the data stream.”
- Streaming submodular maximization: massive data summarization on the fly (2014, background): “[27], or its accelerated variants [24, 22, 3] require random access to the data.”
- Deletion-Robust Submodular Maximization: Data Summarization with "the Right to be Forgotten" (2017, methodology): “Classical methods, such as the celebrated greedy algorithm (Nemhauser et al., 1978) or its accelerated versions (Mirzasoleiman et al., 2015; Badanidiyuru & Vondrák, 2014) require random access to the entire data, make multiple passes, and select elements sequentially in order to produce near…”
- Submodular Maximization in Clean Linear Time (2020, methodology): “The work of Badanidiyuru and Vondrák [4] is probably the first work whose main motivation was to find algorithms with guaranteed approximation ratios for submodular maximization problems that provably enjoy faster time complexities.”
- The Frank-Wolfe Algorithm: A Short Introduction (2023, neutral): “…image processing (see, e.g., Joulin et al. [50], Tang et al. [75]), quantum physics (see, e.g., Gilbert [41], Designolle et al. [30]), submodular function maximization (see, e.g., Feldman et al. [33], Vondrák [79], Badanidiyuru and Vondrák [5], Mirzasoleiman et al. [60], Hassani et al. [45],…”