A Note on the Budgeted Maximization of Submodular Functions

By Andreas Krause, Carlos Guestrin. 2005

179 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, neutral): “Algorithm 6 is closely related to those given by Krause and Guestrin [80] and especially Lin and Bilmes [94].”
Influence Maximization on Social Graphs: A Survey (2018, unknown): “Although this approach could provide arbitrary bad solutions, comparing it with the solution returned by running na € ıve greedy selection until the cost has been exhausted (treating the cost for each node is 1) yields a ð 1 (cid:8) 1 e Þ (cid:8) " approximation ratio [3], [50], [51].”
An Online Algorithm for Maximizing Submodular Functions (2008, methodology): “The problem of maximizing f(S〈T 〉) is a slight generalization of the problem of maximizing a monotone submodular set function subject to a knapsack constraint [14, 20] (which in turn generalizes BUDGETED MAXIMUM COVERAGE [12], which generalizes MAX k-COVERAGE [16]).”
Near-optimal Observation Selection using Submodular Functions (2007, methodology): “These optimization problems are generally NP-hard (Krause & Guestrin 2005b).”
Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints (2013, methodology): “We remark that we can also use a simpler version of the greedy iteration at every iteration [21, 17] and we obtain a guarantee of (1 + , 1/2(1− e−1)).”
Learning Determinantal Point Processes (2011, methodology): “We showed how determinantal point processes can be applied to subset selection tasks like extractive summarization, where negative interactions are key and traditional models like Markov random fields can be computationally problematic.”
Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks (2008, background): “Let A be a solution, and for each sensor location s which is not in A, let ␦ s = R͑A ഫ ͕s͖͒ − R͑A͒ be the improvement in penalty reduction we would get by adding a sensor at location s. Assume we want to place k sensors.”
Multi-document Summarization via Budgeted Maximization of Submodular Functions (2010, methodology): “There is also a greedy algorithm with partial enumerations (Sviridenko, 2004; Krause and Guestrin, 2005) factor (1 − 1 /e ) .”
Algorithmic and Human Teaching of Sequential Decision Tasks (2012, methodology): “While a number of measures are possible (see (Krause and Guestrin 2005a) for an analysis), we use the volume of the space of possible weights.”
Near-optimal sensor placements in Gaussian processes (2005, unknown): “We have recently extended the submodular function maximization approach of Nemhauser et al. (1978) to address this budgeted case (Krause & Guestrin, 2005).”
Cost-effective outbreak detection in networks (2007, background): “Proof: The proof is presented in our technical report [14] Theorem 3 was proved by [13] for the special case of the Budgeted MAX-COVER problem3, and here we prove this result for arbitrary nondecreasing submodular functions.”
Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies (2008, unknown): “(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) = ∑i=1 c(Xi), where A = {X1, .”
Information and Influence Propagation in Social Networks (2013, background): “1 1= p e/ [Krause and Guestrin, 2005], while a more involved and less efficient algorithm can achieve an approximation ratio of 1 1=e [Khuller et al.”
Resource Constrained Neural Network Architecture Search: Will a Submodularity Assumption Help? (2019, background): “[3] prove this result for arbitrary nondecreasing submodular functions.”
Near-optimal Nonmyopic Value of Information in Graphical Models (2005, background): “Hence our algorithms also provide performance guarantees for this important feature selection problem.”