Content deleted Content added
Line 19:
#: 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.
# 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,\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>.
Line 26:
# [[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.
=== Non-monotone Submodular function===
A submodular function <math>f</math> which is not necessarily monotone is called as Non-monotone Submodular function.
| |||