Maximizing Non-Monotone Submodular Functions

By Uriel Feige, Vahab S. Mirrokni, Jan Vondr'ak. 2011

710 citations recorded by the source corpus.

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

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Interpretable Decision Sets: A Joint Framework for Description and Prediction (2016, methodology): “The best known algorithm for maximizing a non-negative, non-normal, non-monotone, and submodular function is smooth local search (SLS) [12].”
Determinantal Point Processes for Machine Learning (2012, background): “[47] showed that even nonmonotone submodular functions can be approximately maximized in polynomial time using a local search algorithm, and a growing body of research has focused on extending this result in a variety of ways [25, 48, 49, 56, 90, 153].”
Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing (2012, background): “We will prove the computational eﬃciency (Lemma 2), the individual rationality (Lemma 3), the proﬁtability (Lemma 4), and the truthfulness (Lemma 5) of the MSensing auction in the following.”
A SAT-Based Approach to Learn Explainable Decision Sets (2018, methodology): “Finally, IDS2, a recent approach [21] based on smooth local search [12], was also tested in the evaluation.”
Learning Mixtures of Submodular Shells with Application to Document Summarization (2012, background): “arbitrary score function. The reason is that the submodular maximization problem, even under many constrained settings, can be solved eciently and near-optimally with rigorous performance guarantees [36, 13, 25, 2, 11]. The hypothesis function we consider takes the following linear discriminant form”
A Survey of Black-Box Adversarial Attacks on Computer Vision Models (2019, background): “2) Bilateral Filter [87]:It is similar to Equation[45] but differs from it in its neighborhood Ω(i), which is a local region (e.”
Optimal marketing strategies over social networks (2008, methodology): “Instead, we use recent work by Feige, Mirrokni, and Vondrak [7] for maximizing non-monotone submodular functions, that gives a deterministic local search 1 3 -approximation algorithm, and a randomized local search 0.”
Reflection methods for user-friendly submodular optimization (2013, neutral): “Generic submodular maximization admits efficient algorithms that can attain approximate optima with global guarantees; these algorithms are typically based on local search techniques [16, 35].”
Submodular Function Maximization (2014, background): “A simple approach towards solving Problem 1 in the case of cardinality constraints is the greedy algorithm , which starts with the empty set S 0 , and in iteration i , adds the element maximizing the discrete derivative ∆( e | S i − 1 ) (ties broken arbitrarily): A celebrated result by Nemhauser et ”
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (2012, neutral): “[11] studied the hardness of USM assuming the function f is given via a value oracle2.”
Very Fast Streaming Submodular Function Maximization (2020, background): “Random has the following properties (Feige et al., 2011): • It outputs a set S such that |S| ≤ K and f(S) ≥ 1 4OPT • It does 1 pass over the data and stores at most O (K) elements Algorithm 2 Random algorithm.”
Submodular Maximization with Cardinality Constraints (2014, background): “2 OF [18]) Let f : 2N → R be submodular.”
Submodular Maximization in Clean Linear Time (2020, background): “[0, 1/4] 0 0 An approximation ratio of 1/4 can be obtained by outputting a uniformly random subset of N [20].”
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].”
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint (2011, background): “[15] give constant factor approximations for the unconstrained problem.”