Submodular set function

In mathematics, submodular functions are set functions which usually appear in approximation algorithms, functions modeling user preferences in game theory. These functions have a natural diminishing returns property which makes them suitable for many applications.

Definition

Submodular function is a set function ${\displaystyle f:2^{\Omega }\rightarrow R}$  which satisfies one of the following equivalent^[1] definitions.

1. For every ${\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)}$ 
2. For every ${\displaystyle S,T\subseteq \Omega }$  we have that ${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$ 
3. For every ${\displaystyle X\subseteq \Omega }$  and ${\displaystyle x_{1},x_{2}\in \Omega \backslash X}$  we have that ${\displaystyle f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)}$ 

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

Examples

1. Linear functions

   Any function of the form ${\displaystyle f(S)=\sum _{i\in S}w_{i}}$  is called a linear function. Additionally if ${\displaystyle \forall i,w_{i}\geq 0}$  then f is montone.

2. Budget-additive functions

   Any function of the form ${\displaystyle f(S)=min(B,\sum _{i\in S}w_{i})}$  for each ${\displaystyle w_{i}\geq 0}$  and ${\displaystyle B\geq 0}$  is called budget additive.

3. Coverage function

   Let ${\displaystyle \Omega =\{e_{1},e_{2},\ldots ,e_{n}\}}$  be the ground set. Consider a universe ${\displaystyle U}$  and a set of sets ${\displaystyle \{E_{1},E_{2},\ldots ,E_{n}\}}$  of the universe ${\displaystyle U}$ . Then a coverage function is defined for any set ${\displaystyle S\subseteq \Omega }$  as ${\displaystyle f(S)=|\cup _{e_{i}\in \Omega }E_{i}|}$ .

4. Entropy

   Let ${\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}$  be a set of random variables. Then for any ${\displaystyle S\subseteq \Omega }$  we have that ${\displaystyle H(S)}$  is a submodular function, where ${\displaystyle H(S)}$  is the entropy of the set of random variables ${\displaystyle S}$ 

5. Graph cuts

   Let ${\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}$  be the vertices of a graph. For any set of vertices ${\displaystyle S\subseteq \Omega }$  let ${\displaystyle f(S)}$  denote the number of edges ${\displaystyle e=(u,v)}$  such that ${\displaystyle u\in S}$  and ${\displaystyle v\in \Omega -S}$ .

6. Mutual information

   Let ${\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}$  be a set of random variables. Then for any ${\displaystyle S\subseteq \Omega }$  we have that ${\displaystyle f(S)=I(S;\Omega -S)}$  is a submodular function, where ${\displaystyle I(S;\Omega -S)}$  is the mutual information.

7. Matroid rank functions

   Let ${\displaystyle \Omega =\{e_{1},e_{2},\dots ,e_{n}\}}$  be the ground set on which a matroid is defined. Then the rank function of the matroid is a submodular function.

Continuous extensions

Lovasz extension

Consider any vector ${\displaystyle {\mathbf {x}}=\{x_{1},x_{2},\dots ,x_{n}\}}$  such that each ${\displaystyle 0\leq x_{i}\leq 1}$ . Then the lovasz extension is defined as ${\displaystyle f^{L}({\mathbf {x}})=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))}$  where the expectation is over choosing ${\displaystyle \lambda }$  uniformly in ${\displaystyle [0,1]}$ .

Multilinear extension

Consider any vector ${\displaystyle {\mathbf {x}}=\{x_{1},x_{2},\ldots ,x_{n}\}}$  such that each ${\displaystyle 0\leq x_{i}\leq 1}$ . Then the multilinear extension is defined as ${\displaystyle F({\mathbf {x}})=\sum _{S\subseteq \Omega }f(S)\prod _{i\in S}x_{i}\prod _{i\notin S}(1-x_{i})}$ 

Optimization problems

Submodular functions have properties which are very similar to convex and concave functions. Hence a lot of optimization problems can be cast as maximizing or minimizing submodular functions subject to various constraints.

1. Minimization of submodular functions.

   Under the simplest case the problem is to find set ${\displaystyle S\subseteq \Omega }$  which minimizes submodular function subject to no constraints. A series of results ^[2][3][4][5] have established the polynomial time solvability of this problem.

2. Maximization of submodular functions.

   Unlike minimization, maximization of submodular functions is typically NP-hard. A host of problems such as max cut, maximum coverage problem can be cast as special cases of this problem under suitable constraints.

References

1. Alexander Schrijver. Combinatorial Optimization, Polyhedra and Efficiency.
2. Grotschel, Lovasz, Schrijver
3. Cunningham
4. Iwata, Fleischer, Fujishige
5. Schrijver

External links

• http://theory.stanford.edu/~jvondrak/CS369P.html
• http://www.cs.illinois.edu/class/sp10/cs598csc/