Submodular set function: Difference between revisions

Revision as of 05:53, 10 February 2012

Revision as of 14:22, 13 February 2012

Line 17:

:Examples of Monotone Submodular function

# Linear functions

#: Any function of the form <math>f(S)=\sum_{i\in S}w_i</math> is called a linear function. Additionally if <math>\forall i,w_i\geq 0</math> then f is montonemonotone.

# Budget-additive functions

#: Any function of the form <math>f(S)=\min(B,\sum_{i\in S}w_i)</math> for each <math>w_i\geq 0</math> and <math>B\geq 0</math> is called budget additive.

Line 66:

# Maximization of submodular functions.

#:Unlike minimization, maximization of submodular functions is typically [[NP-hard]]. A host of problems such as [[max cut]], [[maximum coverage problem]] can be cast as special cases of this problem under suitable constraints. Typically the approximation algorithms for these problems are based on either greedy or local search type of algorithms.

## Maximizing a Symmetric Non-montonemonotone Submodular function subject to no constraint. This problem admits a 1/2 approximation algorithm<ref name="FMV" />. Finding [[max cut]] is a special case of this problem.

## Maximizing a MontoneMonotone Submodular function subject to cardinality constraint. This problem admits a 1-1/e approximation algorithm<ref name="NVF" />. [[Maximum coverage problem]] is a special case of this problem.

==See also==