Non-monotone submodular maximization under matroid and knapsack constraints

Abstract

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. For the problem of maximizing a non-monotone submodular function, Feige, Mirrokni, and Vondrák recently developed a $\frac{2}{5}$-approximation algorithm \cite{FMV07}, however, their algorithms do not handle side constraints.} 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 {\em non-monotone} submodular functions. In particular, for any constant $k$, we present a $(\frac{1}{k+2+\frac{1}{k}+\epsilon })$-approximation for the submodular maximization problem under $k$ matroid constraints, and a $(\frac{1}{5}-\epsilon )$-approximation algorithm for this problem subject to $k$ knapsack constraints ($\epsilon >0$ is any constant). We improve the approximation guarantee of our algorithm to $\frac{1}{k+1+\frac{1}{k-1}+\epsilon }$ for $k\ge 2$ partition matroid constraints. This idea also gives a $(\frac{1}{k+\epsilon })$-approximation for maximizing a {\em monotone} submodular function subject to $k\ge 2$ partition matroids, which improves over the previously best known guarantee of $\frac{1}{k+1}$.

References in corpus (1)

• Submodular approximation: sampling-based algorithms and lower bounds

Cited by in corpus (33)

• Determinantal point processes for machine learning
• Post-hoc explanation of black-box classifiers using confident itemsets
• Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
• Submodular approximation: sampling-based algorithms and lower bounds
• A Directed Graph Fourier Transform with Spread Frequency Components
• Fast Semidifferential-based Submodular Function Optimization
• Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• A $(k+3)/2$-approximation algorithm for monotone submodular maximization over a $k$-exchange system
• A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
• Submodular Optimization under Noise
• Submodular Combinatorial Information Measures with Applications in Machine Learning
• Parameterized Complexity Analysis of Randomized Search Heuristics
• Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms
• Multivariate Submodular Optimization
• Matroid and Knapsack Center Problems
• Robust and Stable Black Box Explanations
• Submodular Norms with Applications To Online Facility Location and Stochastic Probing
• Submodular Function Maximization over Distributive and Integer Lattices
• An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack
• Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm
• Distributed Submodular Maximization
• Optimization with Demand Oracles
• Approximation Schemes for Binary Quadratic Programming Problems with Low cp-Rank Decompositions
• An efficient branch-and-bound algorithm for submodular function maximization
• Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization
• Submodular Maximization Meets Streaming: Matchings, Matroids, and More
• Maximizing Non-Monotone DR-Submodular Functions with Cardinality Constraints
• Maximizing a Submodular Function with Viability Constraints
• Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings
• FPT Approximation Schemes for Maximizing Submodular Functions
• Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions
• Majorisation-minimisation algorithms for minimising the difference between lattice submodular functions