Submodular set function: Difference between revisions

Revision as of 22:27, 1 October 2011

Revision as of 01:08, 3 October 2011

Line 1:

{{Userspace draft|source=ArticleWizard|date=October 2011}} <!-- Please leave this line alone! -->

==Definition==

'''Submodular function''' is a set function <math>f:2^{\Omega}\rightarrow R</math> such that for any <math>X\subseteq Y\subseteq \Omega</math>

and <math>x\in \Omega\backslash Y</math> we have that <math>f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)</math>

Line 6 ⟶ 7:

==Examples==

# Graph cuts

#:Let <math>\Omega=\{v_1,v_2,...,v_n\}</math> be the vertices of a [[graph]]. For any set of vertices <math>S\subseteq \Omega</math> let <math>f(S)</math> denote the number of edges <math>e=(u,v)</math> such that <math>u\in S</math> and <math>v\in \Omega-S</math>.

# Coverage function

#:Let <math>\Omega=\{e_1,e_2,...,e_n\}</math> be the ground set. Consider a universe <math>U</math> and a set of sets <math>\{E_1,E_2,...,E_n\}</math> of the universe <math>U</math>. Then a coverage function is defined for any set <math>S\subseteq \Omega</math> as <math>f(S)=|\cup_{e_i\in \Omega}E_i|</math>.

# [[Entropy (information theory)|Entropy]]

#:Let <math>\Omega=\{X_1,X_2,...,X_n\}</math> be a set of [[random variables]]. Then for any <math>S\subseteq \Omega</math> we have that <math>H(S)</math> is a submodular function, where <math>H(S)</math> is the entropy of the set of random variables <math>S</math>

# [[Mutual information]]

#:Let <math>\Omega=\{X_1,X_2,...,X_n\}</math> be a set of [[random variables]]. Then for any <math>S\subseteq \Omega</math> we have that <math>f(S)=I(S;\Omega-S)</math> is a submodular function, where <math>I(S;\Omega-S)</math> is the mutual information.

# [[Matroid]] rank functions

#:Let <math>\Omega=\{e_1,e_2,...,e_n\}</math> be the ground set on which a matroid is defined. Then the rank function of the matroid is a submodular function.

==Optimization Problems==

Submodular functions have properties which are very similar to convex and concave functions. Hence a lot of optimization problems can be cast as maximizing or minimizing submodular functions subject to various constraints.

# Minimization

# Minimization of Submodular functions.

# Maximization

#:Under the simplest case the problem is to find set <math>S\subseteq \Omega</math> which minimizes submodular function subject to no constraints. A series of results <ref name="GLS" /><ref name="Cunningham" /><ref name="IFF" /><ref name="Schrijver" /> have established the polynomial time solvability of this problem.

# 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.

== References ==

* Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficiency.

{{reflist|

refs=

<ref name="GLS">Grotschel, Lovasz, Schrijver</ref>

<ref name="Cunningham">Cunningham</ref>

<ref name="IFF">Iwata, Fleischer, Fujishige</ref>

<ref name="Schrijver">Schrijver</ref>

}}

== References ==

{{Reflist}}

* Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficiency.

== External links ==