Maximizing Non-monotone Submodular Set Functions Subject to Different Constraints: Combined Algorithms

Abstract

We study the problem of maximizing constrained non-monotone submodular functions and provide approximation algorithms that improve existing algorithms in terms of either the approximation factor or simplicity. Our algorithms combine existing local search and greedy based algorithms. Different constraints that we study are exact cardinality and multiple knapsack constraints. For the multiple-knapsack constraints we achieve a $(0.25-2\epsilon )$-factor algorithm. We also show, as our main contribution, how to use the continuous greedy process for non-monotone functions and, as a result, obtain a $0.13$-factor approximation algorithm for maximization over any solvable down-monotone polytope. The continuous greedy process has been previously used for maximizing smooth monotone submodular function over a down-monotone polytope \cite{CCPV08}. This implies a 0.13-approximation for several discrete problems, such as maximizing a non-negative submodular function subject to a matroid constraint and/or multiple knapsack constraints.

There was an older version of the paper on arXiv. We update it to the latest version. In particular, there was an error in the proof of Theorem 2. We fixed it. The approximation remains the same as before

References in corpus (5)

• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Dependent Randomized Rounding for Matroid Polytopes and Applications
• A note on concentration of submodular functions
• Submodular Functions: Extensions, Distributions, and Algorithms. A Survey
• Approximations for Monotone and Non-monotone Submodular Maximization with Knapsack Constraints

Cited by in corpus (1)

• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes