Content deleted Content added
Yuval Filmus (talk | contribs) m →Non-monotone: Harmonized formatting |
Yuval Filmus (talk | contribs) →Types of submodular functions: Added weights to some of the examples |
||
Line 14:
; Linear functions : 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 monotone.
; 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 functions : Let <math>\Omega=\{E_1,E_2,\ldots,E_n\}</math> be a collection of subsets of some ground set <math>\Omega'</math>. The function <math>f(S)=|\cup_{E_i\in S}E_i|</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>
; [[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.
Line 24:
A non-monotone 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 functions include:
; Graph cuts : Let <math>\Omega=\{v_1,v_2,\dots,v_n\}</math> be the vertices of a [[graph (mathematics)|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>. This can be generalized by adding non-negative weights to the edges.
; [[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 non-monotone submodular function which is not symmetric is called asymmetric.
; Directed cuts : Let <math>\Omega=\{v_1,v_2,\dots,v_n\}</math> be the vertices of a [[directed 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>. This can be generalized by adding non-negative weights to the directed edges.
== Continuous extensions ==
| |||