Submodular set function: Difference between revisions

Revision as of 18:40, 20 August 2019

Revision as of 20:48, 29 August 2019

Line 21:

; Budget-additive functions : Any function of the form <math>f(S)=\min\left\{B,~\sum_{i\in S}w_i\right\}</math> for each <math>w_i\geq 0</math> and <math>B\geq 0</math> is called budget additive.{{citation needed|date=August 2014}}

; Coverage functions : Let <math>\Omega=\{E_1,E_2,\ldots,E_n\}</math> be a collection of subsets of some [[matroid|ground set]] <math>\Omega'</math>. The function <math>f(S)=\left|\bigcup_{E_i\in S}E_i\right|</math> for <math>S\subseteq \Omega</math> is called a coverage function. This can be generalized by adding non-negative weights to the elements.

; [[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>, a fact known as [[Entropic_vector#Shannon-type_inequalities_and_Γn|Shannon's inequality]].<ref>{{Cite web|url = httphttps://www.cs.cmu.edu/~aarti/Class/10704_Spring15/lecs/lec3.pdf|title = Information Processing and Learning|date = |access-date = |website = |publisher = cmu|last = |first = }}</ref> Further inequalities for the entropy function are known to hold, see [[entropic vector]].

; [[Matroid]] [[matroid rank|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.<ref name=F22>Fujishige (2005) p.22</ref>