Content deleted Content added
Mathreader17 (talk | contribs) add reference on Lovász extension |
Mathreader17 (talk | contribs) Add citation to budget-additive function |
||
Line 15:
satisfies the first condition above, but the second condition fails when <math>S</math> and <math>T</math> are infinite sets with finite intersection.
== Types and examples of submodular functions ==
=== Monotone ===
A submodular function <math>f</math> is ''monotone'' if for every <math>T\subseteq S</math> we have that <math>f(T)\leq f(S)</math>. Examples of monotone submodular functions include:
; Linear (Modular) 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 valuation|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.
; 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 = https://www.cs.cmu.edu/~aarti/Class/10704_Spring15/lecs/lec3.pdf|title = Information Processing and Learning|publisher = cmu}}</ref> Further inequalities for the entropy function are known to hold, see [[entropic vector]].
Line 40:
== Continuous extensions ==
=== Generic definition ===
For a submodular function <math>f:2^{\Omega}\rightarrow \mathbb{R}</math> with <math>|\Omega|=n</math>, we can associate each <math>S\subseteq \Omega</math> with a binary vector <math>x^{S}\in \{0, 1\}^{n}</math> such that <math>x_{i}^{S}=1</math> when <math>i\in S</math>, and <math>x_{i}^{S}=0</math> otherwise. In this sense, the submodular function can be seen as a function defined on <math>\{0, 1\}^{n}</math>. We can then define the continuous [[Restriction_(mathematics)#Extension_of_a_function|extension]] of <math>f</math> to be any continuous function <math>F:\mathbb{R}^{n}\rightarrow \mathbb{R}</math> such that it matches the value of the submodular function on <math>x\in \{0, 1\}^{n}</math>, i.e. <math>F(x^{S})=f(S)</math>. Some commonly used continuous extensions are as follows.
Line 106 ⟶ 107:
<ref name="FNS">M. Feldman, J. Naor and R. Schwartz, A unified continuous greedy algorithm for submodular maximization, Proc. of 52nd FOCS (2011).</ref>
<ref name="L">{{cite journal |author-link1=László Lovász |last1=Lovász |first1=L. |date=1983 |title=Submodular functions and convexity |url= |journal=Mathematical Programming The State of the Art |pages=235-257 |doi=10.1007/978-3-642-68874-4_10 }}</ref>
<ref name="BF">{{cite encyclopedia |last1=Buchbinder |first1=Niv |last2=Feldman |first2=Moran |title=Submodular Functions Maximization Problems |encyclopedia= Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications |year=2018 |editor1-last=Gonzalez |editor1-first=Teofilo F. |publisher=Chapman and Hall/CRC |doi=10.1201/9781351236423 |url=https://www.taylorfrancis.com/chapters/edit/10.1201/9781351236423-42/submodular-functions-maximization-problems-niv-buchbinder-moran-feldman}}</ref>
}}
| |||