Submodular set function: Difference between revisions

Revision as of 22:00, 4 October 2011

Revision as of 13:38, 5 October 2011

Line 1:

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

In mathematics, '''Submodularsubmodular functions''' are set functions which usually appear in approximation algorithms, functions modeling user preferences in game theory. These functions have a natural diminishing returns property which makes them suitable for many applications.

==Definition==

Line 17:

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

# Coverage function

#:Let <math>\Omega=\{e_1,e_2,...\ldots,e_n\}</math> be the ground set. Consider a universe <math>U</math> and a set of sets <math>\{E_1,E_2,...\ldots,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,...\ldots,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>

# Graph cuts

#:Let <math>\Omega=\{v_1,v_2,...\dots,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>.

# [[Mutual information]]

#:Let <math>\Omega=\{X_1,X_2,...\ldots,X_n\}</math> be a set of [[random variablesvariable]]s. 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,...\dots,e_n\}</math> be the ground set on which a matroid is defined. Then the rank function of the matroid is a submodular function.

==Continuous Extensionsextensions==

===Lovasz Extensionextension===

Consider any vector <math>\bold{x}=\{x_1,x_2,...\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the lovasz extension is defined as <math>f^L(\bold{x})=\mathbb{E}(f(\{i|x_i\geq \lambda\}))</math> where the expectation is over choosing <math>\lambda</math> uniformly in <math>[0,1]</math>.

===Multilinear Extension===

Consider any vector <math>\bold{x}=\{x_1,x_2,...\ldots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the multilinear extension is defined as <math>F(\bold{x})=\sum_{S\subseteq \Omega} f(S) \Pi_{i\in S} x_i \Pi_{i\notin S} (1-x_i)</math>

==Optimization Problemsproblems==

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 of Submodularsubmodular functions.

#: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 Submodularsubmodular functions.

#:Unlike minimization, maximization of submodular functions is typically [[NP-Hardhard]]. A host of problems such as [[Maxmax cut]], [[Maximummaximum coverage problem]] can be cast as special cases of this problem under suitable constraints.

==References==

Line 50 ⟶ 49:

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

}}

== External links ==