Best Algorithms for Approximating the Maximum of a Submodular Set Function

By George L. Nemhauser, Laurence A. Wolsey. 1978

Subfields: Optimization & Training, Algorithms & Complexity

How researchers see this paper

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

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

Causal Mediation Analysis for Interpreting Neural NLP: The Case of Gender Bias (2020, background): “…submodular functions, it is known that a greedy algorithm that iteratively selects the element with the maximal marginal contribution to its current solution obtains a 1 − 1 /e approximation for maximization under a cardinality constraint (Nemhauser and Wolsey, 1978) and that this bound is optimal.”
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly (2017, methodology): “In general, no polynomial-time algorithm can have a better approximation ratio even for a uniform matroid constraint [Nemhauser andWolsey, 1978; Feige, 1998].”
Submodular Maximization in Clean Linear Time (2020, background): “In their seminal work, Nemhauser and Wolsey [61] and Nemhauser et al.”
Submodularity and Curvature: The Optimal Algorithm (2010, methodology): “This approximation factor is optimal in the value oracle model [ 20 ] and it is optimal even for the explicit special case of Max-k-cover, unless P = NP [8].”
Submodular Function Maximization (2014, background): “Suppose that instead Then a relatively straightforward modiﬁcation of the proof by Nemhauser et al. (1978), which may be found in (Streeter and Golovin, 2008), shows that It turns out that the online greedy algorithm can be interpreted as a noisy version of the (standard) greedy algorithm running…”
Optimal approximation for the submodular welfare problem in the value oracle model (2008, background): “Nemhauser and Wolsey also proved that a better approximation is impossible with a polynomial number of value queries [22].”
Approximation Guarantees for Adaptive Sampling (2018, background): “…the celebrated greedy algorithm which iteratively adds elements whose marginal contribution is largest is known to achieve a 1 1/e approximation (Nemhauser et al., 1978) which is tight unless the algorithm uses exponentially-many queries in the size of the ground set n (Nemhauser & Wolsey, 1978).”
Approximate and Exact Enumeration of Rule Models (2018, unknown): “Lemma 6 (Nemhauser and Wolsey 1978) .”
Robust Optimization for Non-Convex Objectives (2017, background): “Moreover, this approximation ratio is known to be the best possible in polynomial time [15].”
Humpty Dumpty: Controlling Word Meanings via Corpus Poisoning (2020, background): “Such objectives can often be cast as submodular maximization [36, 53] problems, which typically lend themselves well to greedy algorithms.”
Multiwinner Voting with Fairness Constraints (2017, unknown): “S ∆ ≥ 3 ∆ = 1 only ui only ℓi p = O(1) Unconstrained A (1 − 1/e − o(1))-bi (T14) 1 − 1/e (T17) 1 ∆+1 -bi (T15) 1 − 1/e −o(1) (T16) 1 − 1/e (T19) 1 − 1/e [30] C Feasibility NP-hard (T8-10) 1 − 1/e + ε [29] O(log ∆/∆) (T11) Feasibility NP-hard (T9) 1 − 1/e +ε [29] 1 − 1/e + ε [29] Table 1: A summary o”
A Unified Continuous Greedy Algorithm for Submodular Maximization (2011, methodology): “This approach has been used as early as the late 70’s for maximizing monotone submodular functions under the constraint that the solution should be an independent set of one of several specific matroids [12], [20], [24], [25], [27], [32], [42], [43].”
Online Submodular Maximization with Preemption (2015, background): “This result is known to be tight [50], even in the case where the objective function is a coverage function [19].”
Streaming submodular maximization: massive data summarization on the fly (2014, background): “For several classes of monotone submodular functions, it is known that (1− 1/e) is the best approximation guarantee that one can hope for [26, 11, 19].”
( Please , provide the manuscript number ! ) Capacity Constrained Assortment Optimization under the Markov Chain based Choice Model (2015, methodology): “Therefore, from the classical result of Nemhauser and Wolsey (1978) for maximizing a monotone submodular function subject to a cardinality constraint, we know that the greedy algorithm gives a (1− 1/e)-approximation bound for Cardinality-Assort with uniform prices.”
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (2019, methodology): “The (1 − 1 /e ) approximation was shown to be optimal in the value oracle model Nemhauser and Wolsey [1978], but until this work, no stronger hardness result was known for constrained γ -weakly submodular maximization.”
Fast algorithms for maximizing submodular functions (2014, background): “For a long time, the only work in this area had been a sequence of papers by Fisher, Nemhauser and Wolsey [30, 12, 29].”
Investigating Gender Bias in Language Models Using Causal Mediation Analysis (2020, background): “…submodular functions, it is known that a greedy algorithm that iteratively selects the element with the maximal marginal contribution to its current solution obtains a 1 − 1 /e approximation for maximization under a cardinality constraint (Nemhauser and Wolsey, 1978) and that this bound is optimal.”
Lazier Than Lazy Greedy (2014, background): “…would like to choose a summary of a manageable size, a natural optimization problem is to ﬁnd a sum-mary A ∗ of size at most k that maximizes the utility, i.e., (1) Unfortunately, this optimization problem is NP-hard for many classes of submodular functions (Nemhauser and Wolsey 1978; Feige 1998).”
Maximizing Non-Monotone Submodular Functions (2011, methodology): “Again, the greedy algorithm provides a (1 − 1/e)approximation for this problem [39] and this is optimal in the oracle model [40].”