Content deleted Content added
removed unnecessary comment at top of page |
lowercased section headers |
||
Line 10:
==Types==
===Monotone
A submodular function <math>f</math> is said to be monotone if for every <math>T\subseteq S</math> we have that <math>f(T)\leq f(S)</math>.
:Examples of Monotone Submodular function
Line 24:
#: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.
===Non-monotone
A submodular function <math>f</math> which is not necessarily monotone is called as Non-monotone Submodular function.
====Symmetric
A submodular function <math>f</math> is called symmetric if for every <math>S\subseteq \Omega</math> we have that <math>f(S)=f(\Omega-S)</math>
:Examples of Symmetric Non-Monotone Submodular function
Line 33:
# [[Mutual information]]
#:Let <math>\Omega=\{X_1,X_2,\ldots,X_n\}</math> be a set of [[random variable]]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.
====Asymmetric
A submodular function <math>f</math> is called Asymmetric if it is not necessarily symmetric.
:Examples of Symmetric Non-Monotone Submodular function
Line 48:
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 convex closure is defined as <math>f^-(\bold{x})=\min(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\bold{x},\sum_S \alpha_S=1,\alpha_S\geq 0)</math>. It can be shown that <math>f^L(\bold{x})=f^-(\bold{x})</math>
===Concave
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 concave closure is defined as <math>f^+(\bold{x})=\max(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\bold{x},\sum_S \alpha_S=1,\alpha_S\geq 0)</math>.
==Properties==
===Operations which preserve
# Non-negative linear combinations. Consider any submodular function <math>f_1,f_2,\ldots,f_k</math> and non negative numbers <math>\alpha_1,\alpha_2,\ldots,\alpha_k</math>. Then <math>g(S)=\sum_{i=1}^k \alpha_i f_i(S)</math> is a submodular function.
# Consider any monotone submodular function <math>f</math> and a non negative number <math>c</math>. Then <math>g(S)=min(f(S),c)</math> is also a submodular function.
| |||