Submodular set function: Difference between revisions

Revision as of 01:22, 3 October 2011

Revision as of 03:57, 4 October 2011

Line 4:

==Definition==

'''Submodular function''' is a set function <math>f:2^{\Omega}\rightarrow R</math> suchwhich thatsatisfies forone anyof <math>X\subseteqthe Y\subseteqfollowing \Omega''equivalent''</math>ref andname="SchrijverBook" <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>. A submodular function is also a [[subadditive]] function, but a subadditive function need not be submodulardefinitions.

# For every <math>X\subseteq Y\subseteq \Omega</math> and <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>

# For every <math>X\subseteq \Omega</math> and <math>x_1,x_2\in \Omega\backslash X</math> we have that <math>f(X\cup \{x_1\})+f(X\cup \{x_2\})\geq f(X\cup \{x_1,x_2\})+f(X)</math>

A submodular function is also a [[subadditive]] function, but a subadditive function need not be submodular.

==Examples==

Line 27 ⟶ 32:

==References==

*Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficiency.

{{reflist|

refs=

*<ref name="SchrijverBook">Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficiency.</ref>

<ref name="GLS">Grotschel, Lovasz, Schrijver</ref>

<ref name="Cunningham">Cunningham</ref>