Non-monotone submodular maximization under matroid and knapsack constraints

By Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko. 2009

271 citations recorded by the source corpus.

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for non-monotone submodular functions. In particular, for any constant k, we present a (1/k+2+1/k+ε)-approximation for the submodular maximization problem under k matroid constraints, and a (1/5-ε)-approximation algorithm for this problem subject to k knapsack constraints (ε>0 is any constant). We improve the approximation guarantee of our algorithm to 1/k+1+{1/k-1}+ε for k≥2 partition matroid constraints. This idea also gives a ({1/k+ε)-approximation for maximizing a monotone submodular function subject to k≥2 partition matroids, which improves over the previously best known guarantee of 1/k+1.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Mathematical Optimization, 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 Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

Interpretable & Explorable Approximations of Black Box Models (2017, methodology): “Algorithm 1 Optimization Procedure [5]”
"How do I fool you?": Manipulating User Trust via Misleading Black Box Explanations (2019, neutral): “, (k + 2 + 1/k + δ )−1, where k is the number of constraints and δ > 0 [13].”
Determinantal Point Processes for Machine Learning (2012, methodology): “[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].”
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint (2011, methodology): “The multilinear extension has been used also to design approximations for maximizing monotone and non-monotone submodular functions subject to knapsack constraints [29, 30].”
Multi-document Summarization via Budgeted Maximization of Submodular Functions (2010, methodology): “(2009) proposed a cutting-plane method for optimally maximizing a submodular set function under a cardinality constraint, and Lee et.al.”
Joint Task Offloading and Resource Allocation for Multi-Server Mobile-Edge Computing Networks (2017, background): “1For detailed definition of matroid constraint on set function, refer to [42].”
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].”
GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning (2020, background): “Since FLR(S) is a non-monotone submodular function, the resulting problem involves optimizing a non-monotone submodular function subject to matroid base constraints, for which efficient algorithms exist (Lee et al. 2009).”
Faithful and Customizable Explanations of Black Box Models (2019, methodology): “We employ an optimization procedure based on approximate local search (Lee et al. 2009) which provides the best known theoretical guarantees for this class of problems.”
A Unified Continuous Greedy Algorithm for Submodular Maximization (2011, methodology): “Examples of some well-studied problems for which this provides improved approximation are maximization of a non-monotone submodular function f over a single matroid [11], [21], [48] and over O(1) knapsack constraints [11], [33], [36].”
Submodular maximization by simulated annealing (2010, methodology): “2 in [22], f(Sκ) can be compared to any feasible subset of T≤κ(x), e.”