Submodular set function: Difference between revisions

Revision as of 17:10, 16 November 2012

Revision as of 17:21, 16 November 2012

Line 53:

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 [[polynomial time]].<ref name="GLS" /><ref name="Cunningham" /><ref name="IFF" /><ref name="Schrijver" /> Computing the [[minimum cut]] in a graph is a special case of this general minimization problem.

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 - \frac{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" />

== See also ==