A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

By Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz. IEEE Annual Symposium on Foundations of Computer Science, 2012

477 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/b909f818bc903b2db75bd41a6994319351738f02

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

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Submodular Maximization in Clean Linear Time (2020, methodology): “3) O(n) Obtained by the Double Greedy algorithm of [7].”
Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity (2017, methodology): “The gradient-based method in [17] and the double greedy algorithm in [10] are not compared because as reported in [20], they performed worse than ApX.”
Optimizing Ad Allocation in Social Advertising (2015, methodology): “2 Now we are ready to present a linear-time 1/2-approximation algorithm for U-RMP, which is adapted from [30].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “, with non-negative values F (A) for all A ⊆ V ), then simple local search algorithm have led to theoretical guarantees [67, 42, 33].”
Unconstrained Salient Object Detection via Proposal Subset Optimization (2016, background): “Some theoretic approximation analyses for unconstrained submodular maximization [7, 19] may shed light on the good performance of our greedy algorithm.”
Learning the Structure of Deep Convolutional Networks (2015, methodology): “removes) one filter to maximize the gain in optimization, the double greedy [4] GAP algorithm selects the appropriate and non-redundant filters from two complementary directions and thus it can effectively avoid being stuck at a local optimum, as explained in Section 5.”
Fast algorithms for maximizing submodular functions (2014, background): “Extensions and generalizations to nonmonotone submodular functions have been developed in [7, 25, 34, 26, 16, 13, 9, 10, 3, 1].”
RAPID: Rapid and Precise Interpretable Decision Sets (2019, methodology): “In more recent work [34], a 1 / 2 -approximate algorithm for the unconstrained submodular maximization problem has been proposed, we shall refer to this algorithm as USM .”
Video Summarization with Long Short-Term Memory (2016, methodology): “For our dppLSTM, the approximate MAP inference algorithm [46] outputs a subset of selected frames.”
Near-Optimal MAP Inference for Determinantal Point Processes (2012, methodology): “Despite the fact that the symmetric greedy algorithm [18] has an improved approximation guarantee of 1/3, essentially the same analysis applies to Figure 3b.”
Submodular Maximization with Cardinality Constraints (2014, methodology): “This is the second of our two core algorithm and it presents how one can extend the discrete double greedy approach of [8] to the continuous setting, where the sizes of the two evolving sets are more easy to control.”