A note on maximizing a submodular set function subject to a knapsack constraint

By Maxim Sviridenko. Operations Research Letters, 2004

728 citations recorded by the source corpus.

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

View Paper: https://www.semanticscholar.org/paper/973c57fcc6a723cb8e6a313c79f34c108153f0af

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

Diagram Understanding in Geometry Questions (2014, methodology): “This means that there exist a greedy method that finds a (1 − 1/e)-approximation of the global optimum (Nemhauser, Wolsey, and Fisher 1978; Sviridenko 2004).”
Submodular Function Maximization (2014, methodology): “In fact, a more computationally complex algorithm, which enumerates all sets S of size 3, and augments them using the cost-beneﬁt greedy algorithm, is known to provide a 1 − 1 /e approximation (Sviridenko, 2004).”
Client Selection for Federated Learning with Heterogeneous Resources in Mobile Edge (2018, methodology): “To this end, we propose a heuristic algorithm based on the greedy algorithm for a maximization problem with a knapsack constraint [14].”
A Note on the Budgeted Maximization of Submodular Functions (2005, neutral): “Keywords: Submodular functions; Optimization; Constraints; Entropy maximization”
Near-optimal Nonmyopic Value of Information in Graphical Models (2005, methodology): “Building on recent constant-factor approximation algorithms for maximizing submodular functions where elements have different costs [ 18 , 14], we extend our approach to problems where possible observations have different costs.”
An Online Algorithm for Maximizing Submodular Functions (2008, methodology): “We then present a greedy approximation algorithm that simultaneously achieves the optimal approximation ratios (of 4 and 1 − 1e ) for these two problems, building on and generalizing previous work on special cases of these two problems [7, 20].”
Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies (2008, positive): “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…”
A submodular optimization approach to sentence set selection (2014, methodology): “To the best of our knowledge, the submodular optimization techniques have never been applied to the phonetically-balanced sentence set selection problem in the literature.”
Model-based Diagnosis of Hybrid Systems (2009, background): “If we are willing to pay O(T n 4 ), we can also get an (1 − 1 e ) approximation [Sviridenko, 2004] .”
Submodular Maximization in Clean Linear Time (2020, methodology): “The algorithm of Sviridenko [62] is based on making 3 guesses.”
Near-optimal Observation Selection using Submodular Functions (2007, methodology): “…a slight modification of the algorithm, combining the greedy selection of the location with highest benefitcost ratio sj = argmaxs F (A∪{s})−F (A) c(s) , with a partial enumeration scheme achieves the same constant factor (1 − 1/e) approximation guarantee (Sviridenko 2004; Krause & Guestrin 2005a).”
Fast algorithms for maximizing submodular functions (2014, methodology): “The n(5)-time algorithm from [32, 19] works as follows.”
Maximizing Non-Monotone Submodular Functions (2011, background): “More generally, a (1 − 1/e)-approximation can be achieved for monotone submodular maximization under a knapsack constraint [46].”
HFEL: Joint Edge Association and Resource Allocation for Cost-Efficient Hierarchical Federated Edge Learning (2020, background): “Unfortunately, FL suffers from a bottleneck of communication and energy overhead before reaching a satisfactory model accuracy due to long transmission latency in wide area network (WAN) [9].”
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 ) .”
Cost-effective outbreak detection in networks (2007, background): “The first approximation results about maximizing submodular functions in the non-constant cost case were proved by [ 25 ].”
A Class of Submodular Functions for Document Summarization (2011, methodology): “In this case as well, however, a modified greedy algorithm with partial enumeration can solve Problem 1 near-optimally with (1−1/e)-approximation factor ifF is monotone submodular (Sviridenko, 2004).”
Submodular secretary problem and extensions (2010, methodology): “A (1 - 1/e) approximation has been also obtained for a knapsack constraint [Sviridenko 2004], and for a special class of submodular functions under a matroid constraint [Calinescu et al. 2007].”