Submodular set function: Difference between revisions

Revision as of 22:26, 1 October 2011

Revision as of 22:27, 1 October 2011

Line 2:

'''Submodular function''' is a set function <math>f:2^{\Omega}\rightarrow R</math> such that for any <math>X\subseteq Y\subseteq \Omega</math>

and <math>x\in \Omega\backslash XY</math> we have that <math>f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)</math>

==Examples==