Submodular set function

Submodular functions ...

A submodular function is a set function $f:2^{\Omega }\rightarrow R$ such that for any $X\subseteq Y\subseteq \Omega$ and $x\in \Omega \backslash X$ we have that $f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)$

Examples

1. Graph cuts
2. Coverage function
3. Entropy
4. Mututal Information

References

• Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficiency.

External links

• example.com