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.

1 Definition
2 Applications
3 Types
- 3.1 Monotone Submodular function
- 3.2 Non-monotone Submodular function
  - 3.2.1 Symmetric Non-monotone Submodular function
  - 3.2.2 Asymmetric Non-monotone Submodular function
4 Continuous extensions
5 Properties
- 5.1 Operations which preserve Submodularity
6 Optimization problems
7 See also
8 Citations
9 References
- 9.1 General References

Definition

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

For every $X\subseteq Y\subseteq \Omega$ and $x\in \Omega\backslash Y$ we have that $f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)$
For every $S,T\subseteq \Omega$ we have that $f(S)%2Bf(T)\geq f(S\cup T)%2Bf(S\cap T)$
For every $X\subseteq \Omega$ and $x_1,x_2\in \Omega\backslash X$ we have that $f(X\cup \{x_1\})%2Bf(X\cup \{x_2\})\geq f(X\cup \{x_1,x_2\})%2Bf(X)$

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

Applications

Types

Monotone Submodular function

A submodular function $f$ is said to be monotone if for every $T\subseteq S$ we have that $f(T)\leq f(S)$ .

Examples of Monotone Submodular function

Linear functions

Any function of the form $f(S)=\sum_{i\in S}w_i$ is called a linear function. Additionally if $\forall i,w_i\geq 0$ then f is montone.
Budget-additive functions

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

Let $\Omega=\{e_1,e_2,\ldots,e_n\}$ be the ground set. Consider a universe $U$ and a set of sets $\{E_1,E_2,\ldots,E_n\}$ of the universe $U$ . Then a coverage function is defined for any set $S\subseteq \Omega$ as $f(S)=|\cup_{e_i\in \Omega}E_i|$ .
Entropy

Let $\Omega=\{X_1,X_2,\ldots,X_n\}$ be a set of random variables. Then for any $S\subseteq \Omega$ we have that $H(S)$ is a submodular function, where $H(S)$ is the entropy of the set of random variables $S$
Matroid rank functions

Let $\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.

Non-monotone Submodular function

A submodular function $f$ which is not necessarily monotone is called as Non-monotone Submodular function.

Symmetric Non-monotone Submodular function

A submodular function $f$ is called symmetric if for every $S\subseteq \Omega$ we have that $f(S)=f(\Omega-S)$

Examples of Symmetric Non-Monotone Submodular function

Graph cuts

Let $\Omega=\{v_1,v_2,\dots,v_n\}$ be the vertices of a graph. For any set of vertices $S\subseteq \Omega$ let $f(S)$ denote the number of edges $e=(u,v)$ such that $u\in S$ and $v\in \Omega-S$ .
Mutual information

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

Asymmetric Non-monotone Submodular function

A submodular function $f$ is called Asymmetric if it is not necessarily symmetric.

Examples of Symmetric Non-Monotone Submodular function

Directed graph cuts

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

Continuous extensions

Lovasz extension

Consider any vector $\bold{x}=\{x_1,x_2,\dots,x_n\}$ such that each $0\leq x_i\leq 1$ . Then the lovasz extension is defined as $f^L(\bold{x})=\mathbb{E}(f(\{i|x_i\geq \lambda\}))$ where the expectation is over choosing $\lambda$ uniformly in $[0,1]$ . It can be shown that Lovasz extension is a convex function.

Multilinear extension

Consider any vector $\bold{x}=\{x_1,x_2,\ldots,x_n\}$ such that each $0\leq x_i\leq 1$ . Then the multilinear extension is defined as $F(\bold{x})=\sum_{S\subseteq \Omega} f(S) \prod_{i\in S} x_i \prod_{i\notin S} (1-x_i)$

Convex Closure

Consider any vector $\bold{x}=\{x_1,x_2,\dots,x_n\}$ such that each $0\leq x_i\leq 1$ . Then the convex closure is defined as $f^-(\bold{x})=min(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\bold{x},\sum_S \alpha_S=1,\alpha_S\geq 0)$ . It can be shown that $f^L(\bold{x})=f^-(\bold{x})$

Concave Closure

Consider any vector $\bold{x}=\{x_1,x_2,\dots,x_n\}$ such that each $0\leq x_i\leq 1$ . Then the convex closure is defined as $f^%2B(\bold{x})=max(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\bold{x},\sum_S \alpha_S=1,\alpha_S\geq 0)$ .

Properties

Operations which preserve Submodularity

Non-negative linear combinations. Consider any submodular function $f_1,f_2,\ldots,f_k$ and non negative numbers $\alpha_1,\alpha_2,\ldots,\alpha_k$ . Then $g(S)=\sum_{i=1}^k \alpha_i f_i(S)$ is a submodular function.
Consider any monotone submodular function $f$ and a non negative number $c$ . Then $g(S)=min(f(S),c)$ is also a submodular function.
Consider any submodular function $f$ . Then $g(S)=f(\Omega-S)$ is also a submodular function.

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.

Minimization of submodular functions.

Under the simplest case the problem is to find set $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. Finding minimum cut in a graph is a special case of this problem.
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. Typically the approximation algorithms for these problems are based on either greedy or local search type of algorithms.
1. Maximizing a Symmetric Non-montone Submodular function subject to no constraint. This problem admits a 1/2 approximation algorithm^[6]. Finding max cut is a special case of this problem.
2. Maximizing a Montone Submodular function subject to cardinality constraint. This problem admits a 1-1/e approximation algorithm^[7]. Maximum coverage problem is a special case of this problem.

Citations

^ (Schrijver 2003, §44, p. 766)
^ M. Grotschel, L. Lovasz, and A. Schrijver , The ellipsoid method and its consequences in combinatorial optimization,Combinatorica,1 (1981),pp. 169–197.
^ W. H. Cunningham, On submodular function minimization, Combinatorica,5 (1985),pp. 185–192.
^ S. Iwata, L. Fleischer, and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions,J. ACM,48 (2001),pp. 761–777
^ A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time,J. Combin. Theory Ser. B,80 (2000),pp. 346–355.
^ U. Feige, V. Mirrokni and J. Vondr´ak. Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), 461–471.
^ G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I, Mathematical Programming 14 (1978), 265–294

References

General References

Schrijver, Alexander (2003), Combinatorial Optimization, Springer, ISBN 3540443894
Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge University Press, ISBN 0521010128
Fujishige, Saruto (2005), Submodular Functions and Optimization, Elsevier, ISBN 0444520864
Narayanan, H. (1997), Submodular Functions and Electrical Networks, ISBN 0444825231