Content deleted Content added
Expanded definition |
added more examples, continuous extensions and external links |
||
Line 12:
==Examples==
# Linear functions
# Graph cuts▼
#: 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 montone.
#: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>.▼
# 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.
# 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>
▲# 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>.
# [[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.
==Continuous Extensions==
===Lovasz Extension===
Consider any vector <math>\bold{x}=\{x_1,x_2,...,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,...,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 Problems==
Line 46 ⟶ 56:
== External links ==
* http://theory.stanford.edu/~jvondrak/CS369P.html
* http://www.cs.illinois.edu/class/sp10/cs598csc/
<!--- Categories --->
| |||