Computer Science – Data Structures and Algorithms
Scientific paper
2011-01-15
Computer Science
Data Structures and Algorithms
Scientific paper
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.
Fadaei Salman
Fazli MohammadAmin
Safari MohammadAli
No associations
LandOfFree
Maximizing Non-monotone Submodular Set Functions Subject to Different Constraints: Combined Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maximizing Non-monotone Submodular Set Functions Subject to Different Constraints: Combined Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximizing Non-monotone Submodular Set Functions Subject to Different Constraints: Combined Algorithms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-227996