Content deleted Content added
changed link to subadditive to Subadditive set function |
→Optimization problems: strongly polynomial running time for minimization |
||
Line 50:
Submodular functions have properties which are very similar to [[convex function|convex]] and [[concave function]]s. For this reason, an [[optimization problem]] which concerns optimizing a convex or concave function can also be described as the problem of maximizing or minimizing a submodular function subject to some constraints.
The simplest minimization problem is to find a set <math>S\subseteq \Omega</math> which minimizes a submodular function subject to no constraints. This problem is computable in
Unlike minimization, maximization of submodular functions is usually [[NP-hard]]. Many problems, such as [[max cut]] and the [[maximum coverage problem]], can be cast as special cases of this general maximization problem under suitable constraints. Typically, the approximation algorithms for these problems are based on either [[greedy algorithm]]s or [[local search (optimization)|local search algorithm]]s. The problem of maximizing a symmetric non-monotone submodular function subject to no constraints admits a 1/2 approximation algorithm.<ref name="FMV" /> Computing the [[maximum cut]] of a graph is a special case of this problem. The more general problem of maximizing an arbitrary non-monotone submodular function subject to no constraints also admits a 1/2 approximation algorithm.<ref name="BFNS" /> The problem of maximizing a monotone submodular function subject to a cardinality constraint admits a <math>1 - 1/e</math> approximation algorithm.<ref name="NVF" /> The [[maximum coverage problem]] is a special case of this problem. The more general problem of maximizing a monotone submodular function subject to a [[matroid]] constraint also admits a <math>1 - 1/e</math> approximation algorithm.<ref name="CCPV" /><ref name="FW" />
| |||