An analysis of approximations for maximizing submodular set functions—I

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

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

Citations in the corpus

Data-Efficient Structured Pruning via Submodular Optimization (2022, background): “The returned solution is guaranteed to satisfy F ( ˆ S ) ≥ (1 − 1 /e ) max | S |≤ k F ( S ) [Nemhauser et al., 1978].”
Machine Teaching: An Inverse Problem to Machine Learning and an Approach Toward Optimal Education (2015, methodology): “Discrete optimization methods, such as those based on submodularity, may be applicable here (Krause and Golovin 2014; Iyer and Bilmes 2013; Bach 2013; Feige 1998; Krause and Guestrin 2005; Nemhauser, Wolsey, and Fisher 1978).”
Determinantal Point Processes for Machine Learning (2012, background): “…can be minimized in polynomial time [Schrijver, 2000], and many results exist for approximately maximizing monotone submodular functions, which have the special property that supersets always have higher function values than their subsets [Nemhauser et al., 1978, Fisher et al., 1978, Feige, 1998].”
Scalable Influence Estimation in Continuous-Time Diffusion Networks (2013, background): “The greedy algorithm finds a source node set which achieves at least a constant fraction (1 − 1/e) of the optimal [18].”
Multi-Scale Representation Learning on Proteins (2022, methodology): “Both terms satisfy monotonicity and submodularity and can thus be efﬁciently optimized based on techniques from submodular optimization [Nemhauser et al., 1978].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “As we show below, it has an (1 − 1/e)-performance guarantee [166].”
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly (2017, methodology): “Submodular set function maximization has been well studied, beginning with the classical analysis of the greedy forward selection algorithm subject to a matroid constraint [Nemhauser et al., 1978; Fisher et al., 1978].”
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting (2009, methodology): “This is because F ( A ) satisﬁes a diminishing returns property called submodularity (Krause & Guestrin, 2005), and the greedy approximation guarantee (5) holds for any submodular function (Nemhauser et al., 1978).”
Non-monotone submodular maximization under matroid and knapsack constraints (2009, background): “A simple consequence of Lemma 1 implies bounds analogous to known approximation factors [40, 43] in the cases when the submodular function f has additional structure.”
Topic-aware social influence propagation models (2012, unknown): “When equipped with such properties, the simple greedy algorithm that at each iteration greedily extends the set of seeds with the node providing the largest marginal gain, produces a solution with provable approximation guarantee (1 − 1/e) [5].”
FemtoCaching: Wireless video content delivery through distributed caching helpers (2011, background): “Classical results on approximations of submodular functions [13] established that the greedy”
Guarantees for Greedy Maximization of Non-submodular Functions with Applications (2017, background): “decreasing submodular set function1, the GREEDY algorithm enjoys the multiplicative approximation guarantee of (1 − 1/e) (Nemhauser et al., 1978; Sviridenko, 2004; Vondrák, 2008; Krause & Golovin, 2012).”
Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies (2008, unknown): “Recently, the submodular function maximization approach of Nemhauser et al. (1978) has been extended to address this budgeted case (Sviridenko, 2004; Krause and Guestrin, 2005), in the case of modular cost functions, that is, c(A) = ∑ k i=1 c(X i ), where A = {X 1 , . . . , X k } and c(X i ) is the…”
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (2018, background): “In terms of parallel running time, this is exponentially faster than the celebrated greedy algorithm which gives a (1 − 1/e)-approximation in O(k) rounds (Nemhauser et al., 1978).”
Classification of Hyperspectral Images by Exploiting Spectral–Spatial Information of Superpixel via Multiple Kernels (2015, background): “The problem (7) can be efficiently solved by a greedy algorithm introduced in [37].”