Submodular set function

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

Examples

1. Graph cuts
2. Coverage function
3. Entropy
4. Mutual information
5. Matroid rank functions

Optimization Problems

1. Minimization
2. Maximization

References

• Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficiency.

External links