Content deleted Content added
A bunch of changes to improve readability, remove ordered lists where no order was necessary, clarify sentences which include both math and English, etc. |
m disambiguating links |
||
Line 2:
== Definition ==
If <math>\Omega</math> is a [[set (mathematics)|set]], a submodular function is a set function <math>f:2^{\Omega}\rightarrow \mathbb{R}</math>, where <math>2^\Omega</math> denotes the [[Power set#Representing subsets as functions|power set]] of <math>\Omega</math>, which satisfies one of the following equivalent definitions<ref>{{Harvard citations|last = Schrijver|year = 2003|loc = §44, p. 766|nb = }}</ref>.
# For every <math>X, Y \subseteq \Omega</math> with <math> X \subseteq Y</math> and every <math>x \in \Omega \backslash Y</math> we have that <math>f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)</math>.
# For every <math>S, T \subseteq \Omega</math> we have that <math>f(S)+f(T)\geq f(S\cup T)+f(S\cap T)</math>.
Line 34:
== Continuous extensions ==
=== Lovász extension ===
This extension is named after mathematician [[László Lovász]]. Consider any vector <math>\bold{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the Lovász extension is defined as <math>f^L(\bold{x})=\mathbb{E}(f(\{i|x_i\geq \lambda\}))</math> where the expectation is over <math>\lambda</math> chosen from the [[uniform distribution (continuous)|uniform distribution]] on the interval <math>[0,1]</math>. The Lovász extension is a convex function.
=== Multilinear extension ===
| |||