Submodular set function: Difference between revisions

Revision as of 13:13, 7 May 2012

Revision as of 18:04, 2 July 2012

Line 21:

#: 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_1E_1,e_2E_2,\ldots,e_nE_n\}</math> be thea groundcollection set.of Considersubsets aof universesome ground set <math>U\Omega'</math>. andThe a set of setsfunction <math>f(S)=|\cup_{E_1,E_2,\ldots,E_nE_i\in S}E_i|</math> of the universe <math>U</math>. Then a coverage function is defined for any set <math>S\subseteq \Omega</math> asis <math>f(S)=|\cup_{e_i\incalled \Omega}E_i|</math>a coverage function.

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