:Submodular set function

If $\backslash Omega$ is a finite set, a submodular function is a set function $f:2^\{\backslash Omega\}\backslash rightarrow\; \backslash mathbb\{R\}$, where $2^\backslash Omega$ denotes the power set of $\backslash Omega$, which satisfies one of the following equivalent conditions.{{Harvard citations|last = Schrijver|year = 2003|loc = §44, p. 766|nb = }}

1. For every $X,\; Y\; \backslash subseteq\; \backslash Omega$ with $X\; \backslash subseteq\; Y$ and every $x\; \backslash in\; \backslash Omega\; \backslash setminus\; Y$ we have that $f(X\backslash cup\; \backslash \{x\backslash \})-f(X)\backslash geq\; f(Y\backslash cup\; \backslash \{x\backslash \})-f(Y)$.
2. For every $S,\; T\; \backslash subseteq\; \backslash Omega$ we have that $f(S)+f(T)\backslash geq\; f(S\backslash cup\; T)+f(S\backslash cap\; T)$.
3. For every $X\backslash subseteq\; \backslash Omega$ and $x\_1,x\_2\backslash in\; \backslash Omega\backslash backslash\; X$ such that $x\_1\backslash neq\; x\_2$ we have that $f(X\backslash cup\; \backslash \{x\_1\backslash \})+f(X\backslash cup\; \backslash \{x\_2\backslash \})\backslash geq\; f(X\backslash cup\; \backslash \{x\_1,x\_2\backslash \})+f(X)$.

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

If $\backslash Omega$ is not assumed finite, then the above conditions are not equivalent. In particular a function

$f$ defined by $f(S)\; =\; 1$ if $S$ is finite and $f(S)\; =\; 0$ if $S$ is infinite

satisfies the first condition above, but the second condition fails when $S$ and $T$ are infinite sets with finite intersection.

A set function $f$ is monotone if for every $T\backslash subseteq\; S$ we have that $f(T)\backslash leq\; f(S)$. Examples of monotone submodular functions include:

; Linear (Modular) functions : Any function of the form $f(S)=\backslash sum\_\{i\backslash in\; S\}w\_i$ is called a linear function. Additionally if $\backslash forall\; i,w\_i\backslash geq\; 0$ then f is monotone.

; Budget-additive functions : Any function of the form $f(S)=\backslash min\backslash left\backslash \{B,~\backslash sum\_\{i\backslash in\; S\}w\_i\backslash right\backslash \}$ for each $w\_i\backslash geq\; 0$ and $B\backslash geq\; 0$ is called budget additive.

; Coverage functions : Let $\backslash Omega=\backslash \{E\_1,E\_2,\backslash ldots,E\_n\backslash \}$ be a collection of subsets of some ground set $\backslash Omega\text{'}$. The function $f(S)=\backslash left|\backslash bigcup\_\{E\_i\backslash in\; S\}E\_i\backslash right|$ for $S\backslash subseteq\; \backslash Omega$ is called a coverage function. This can be generalized by adding non-negative weights to the elements.

; Entropy : Let $\backslash Omega=\backslash \{X\_1,X\_2,\backslash ldots,X\_n\backslash \}$ be a set of random variables. Then for any $S\backslash subseteq\; \backslash Omega$ we have that $H(S)$ is a submodular function, where $H(S)$ is the entropy of the set of random variables $S$, a fact known as Shannon's inequality.{{Cite web|url = https://www.cs.cmu.edu/~aarti/Class/10704_Spring15/lecs/lec3.pdf|title = Information Processing and Learning|publisher = cmu}} Further inequalities for the entropy function are known to hold, see entropic vector.

; Matroid rank functions : Let $\backslash Omega=\backslash \{e\_1,e\_2,\backslash dots,e\_n\backslash \}$ be the ground set on which a matroid is defined. Then the rank function of the matroid is a submodular function.Fujishige (2005) p.22

A submodular function that is not monotone is called non-monotone. In particular, a function is called non-monotone if it has the property that adding more elements to a set can decrease the value of the function. More formally, the function $f$ is non-monotone if there are sets $S,T$ in its domain s.t. $S\; \backslash subset\; T$ and $f(S)>\; f(T)$.

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

Examples of symmetric non-monotone submodular functions include:

; Graph cuts : Let $\backslash Omega=\backslash \{v\_1,v\_2,\backslash dots,v\_n\backslash \}$ be the vertices of a graph. For any set of vertices $S\backslash subseteq\; \backslash Omega$ let $f(S)$ denote the number of edges $e=(u,v)$ such that $u\backslash in\; S$ and $v\backslash in\; \backslash Omega-S$. This can be generalized by adding non-negative weights to the edges.

; Mutual information : Let $\backslash Omega=\backslash \{X\_1,X\_2,\backslash ldots,X\_n\backslash \}$ be a set of random variables. Then for any $S\backslash subseteq\; \backslash Omega$ we have that $f(S)=I(S;\backslash Omega-S)$ is a submodular function, where $I(S;\backslash Omega-S)$ is the mutual information.

A non-monotone submodular function which is not symmetric is called asymmetric.

; Directed cuts : Let $\backslash Omega=\backslash \{v\_1,v\_2,\backslash dots,v\_n\backslash \}$ be the vertices of a directed graph. For any set of vertices $S\backslash subseteq\; \backslash Omega$ let $f(S)$ denote the number of edges $e=(u,v)$ such that $u\backslash in\; S$ and $v\backslash in\; \backslash Omega-S$. This can be generalized by adding non-negative weights to the directed edges.

Often, given a submodular set function that describes the values of various sets, we need to compute the values of fractional sets. For example: we know that the value of receiving house A and house B is V, and we want to know the value of receiving 40% of house A and 60% of house B. To this end, we need a continuous extension of the submodular set function.

Formally, a set function $f:2^\{\backslash Omega\}\backslash rightarrow\; \backslash mathbb\{R\}$ with $|\backslash Omega|=n$ can be represented as a function on $\backslash \{0,\; 1\backslash \}^\{n\}$, by associating each $S\backslash subseteq\; \backslash Omega$ with a binary vector $x^\{S\}\backslash in\; \backslash \{0,\; 1\backslash \}^\{n\}$ such that $x\_\{i\}^\{S\}=1$ when $i\backslash in\; S$, and $x\_\{i\}^\{S\}=0$ otherwise. A continuous extension of $f$ is a continuous function $F:[0,\; 1]^\{n\}\backslash rightarrow\; \backslash mathbb\{R\}$, that matches the value of $f$ on $x\backslash in\; \backslash \{0,\; 1\backslash \}^\{n\}$, i.e. $F(x^\{S\})=f(S)$.

Several kinds of continuous extensions of submodular functions are commonly used, which are described below.

This extension is named after mathematician László Lovász. Consider any vector $\backslash mathbf\{x\}=\backslash \{x\_1,x\_2,\backslash dots,x\_n\backslash \}$ such that each $0\backslash leq\; x\_i\backslash leq\; 1$. Then the Lovász extension is defined as

$f^L(\backslash mathbf\{x\})=\backslash mathbb\{E\}(f(\backslash \{i|x\_i\backslash geq\; \backslash lambda\backslash \}))$

where the expectation is over $\backslash lambda$ chosen from the uniform distribution on the interval $[0,1]$. The Lovász extension is a convex function if and only if $f$ is a submodular function.

Consider any vector $\backslash mathbf\{x\}=\backslash \{x\_1,x\_2,\backslash ldots,x\_n\backslash \}$ such that each $0\backslash leq\; x\_i\backslash leq\; 1$. Then the multilinear extension is defined as {{Cite book |last=Vondrak |first=Jan |title=Proceedings of the fortieth annual ACM symposium on Theory of computing |chapter=Optimal approximation for the submodular welfare problem in the value oracle model |date=2008-05-17 |chapter-url=https://doi.org/10.1145/1374376.1374389 |series=STOC '08 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=67–74 |doi=10.1145/1374376.1374389 |isbn=978-1-60558-047-0|s2cid=170510 }}{{Cite journal |last1=Calinescu |first1=Gruia |last2=Chekuri |first2=Chandra |last3=Pál |first3=Martin |last4=Vondrák |first4=Jan |date=January 2011 |title=Maximizing a Monotone Submodular Function Subject to a Matroid Constraint |url=http://epubs.siam.org/doi/10.1137/080733991 |journal=SIAM Journal on Computing |language=en |volume=40 |issue=6 |pages=1740–1766 |doi=10.1137/080733991 |issn=0097-5397|url-access=subscription }}$F(\backslash mathbf\{x\})=\backslash sum\_\{S\backslash subseteq\; \backslash Omega\}\; f(S)\; \backslash prod\_\{i\backslash in\; S\}\; x\_i\; \backslash prod\_\{i\backslash notin\; S\}\; (1-x\_i)$.

Intuitively, x_i represents the probability that item i is chosen for the set. For every set S, the two inner products represent the probability that the chosen set is exactly S. Therefore, the sum represents the expected value of f for the set formed by choosing each item i at random with probability xi, independently of the other items.

Consider any vector $\backslash mathbf\{x\}=\backslash \{x\_1,x\_2,\backslash dots,x\_n\backslash \}$ such that each $0\backslash leq\; x\_i\backslash leq\; 1$. Then the convex closure is defined as $f^-(\backslash mathbf\{x\})=\backslash min\backslash left(\backslash sum\_S\; \backslash alpha\_S\; f(S):\backslash sum\_S\; \backslash alpha\_S\; 1\_S=\backslash mathbf\{x\},\backslash sum\_S\; \backslash alpha\_S=1,\backslash alpha\_S\backslash geq\; 0\backslash right)$.

The convex closure of any set function is convex over $[0,1]^n$.

Consider any vector $\backslash mathbf\{x\}=\backslash \{x\_1,x\_2,\backslash dots,x\_n\backslash \}$ such that each $0\backslash leq\; x\_i\backslash leq\; 1$. Then the concave closure is defined as $f^+(\backslash mathbf\{x\})=\backslash max\backslash left(\backslash sum\_S\; \backslash alpha\_S\; f(S):\backslash sum\_S\; \backslash alpha\_S\; 1\_S=\backslash mathbf\{x\},\backslash sum\_S\; \backslash alpha\_S=1,\backslash alpha\_S\backslash geq\; 0\backslash right)$.

For the extensions discussed above, it can be shown that $f^\{+\}(\backslash mathbf\{x\})\; \backslash geq\; F(\backslash mathbf\{x\})\; \backslash geq\; f^\{-\}(\backslash mathbf\{x\})=f^L(\backslash mathbf\{x\})$ when $f$ is submodular.

1. The class of submodular functions is closed under non-negative linear combinations. Consider any submodular function $f\_1,f\_2,\backslash ldots,f\_k$ and non-negative numbers $\backslash alpha\_1,\backslash alpha\_2,\backslash ldots,\backslash alpha\_k$. Then the function $g$ defined by $g(S)=\backslash sum\_\{i=1\}^k\; \backslash alpha\_i\; f\_i(S)$ is submodular.
2. For any submodular function $f$, the function defined by $g(S)=f(\backslash Omega\; \backslash setminus\; S)$ is submodular.
3. The function $g(S)=\backslash min(f(S),c)$, where $c$ is a real number, is submodular whenever $f$ is monotone submodular. More generally, $g(S)=h(f(S))$ is submodular, for any non decreasing concave function $h$.
4. Consider a random process where a set $T$ is chosen with each element in $\backslash Omega$ being included in $T$ independently with probability $p$. Then the following inequality is true $\backslash mathbb\{E\}[f(T)]\backslash geq\; p\; f(\backslash Omega)+(1-p)\; f(\backslash varnothing)$ where $\backslash varnothing$ is the empty set. More generally consider the following random process where a set $S$ is constructed as follows. For each of $1\backslash leq\; i\backslash leq\; l,\; A\_i\backslash subseteq\; \backslash Omega$ construct $S\_i$ by including each element in $A\_i$ independently into $S\_i$ with probability $p\_i$. Furthermore let $S=\backslash cup\_\{i=1\}^l\; S\_i$. Then the following inequality is true $\backslash mathbb\{E\}[f(S)]\backslash geq\; \backslash sum\_\{R\backslash subseteq\; [l]\}\; \backslash Pi\_\{i\backslash in\; R\}p\_i\; \backslash Pi\_\{i\backslash notin\; R\}(1-p\_i)f(\backslash cup\_\{i\backslash in\; R\}A\_i)$.{{Citation needed|date=November 2013}}

Submodular functions have properties which are very similar to convex and concave functions. For this reason, an optimization problem which concerns optimizing a convex or concave function can also be described as the problem of maximizing or minimizing a submodular function subject to some constraints.

The hardness of minimizing a submodular set function depends on constraints imposed on the problem.

1. The unconstrained problem of minimizing a submodular function is computable in polynomial time, and even in strongly-polynomial time. Computing the minimum cut in a graph is a special case of this minimization problem.
2. The problem of minimizing a submodular function with a cardinality lower bound is NP-hard, with polynomial factor lower bounds on the approximation factor.

Unlike the case of minimization, maximizing a generic submodular function is NP-hard even in the unconstrained setting. Thus, most of the works in this field are concerned with polynomial-time approximation algorithms, including greedy algorithms or local search algorithms.

1. The problem of maximizing a non-negative submodular function admits a 1/2 approximation algorithm. Computing the maximum cut of a graph is a special case of this problem.
2. The problem of maximizing a monotone submodular function subject to a cardinality constraint admits a $1\; -\; 1/e$ approximation algorithm.{{Cite web|last=Williamson|first=David P.|title=Bridging Continuous and Discrete Optimization: Lecture 23|url=https://people.orie.cornell.edu/dpw/orie6334/lecture23.pdf}} The maximum coverage problem is a special case of this problem.
3. The problem of maximizing a monotone submodular function subject to a matroid constraint (which subsumes the case above) also admits a $1\; -\; 1/e$ approximation algorithm.

Many of these algorithms can be unified within a semi-differential based framework of algorithms.

Apart from submodular minimization and maximization, there are several other natural optimization problems related to submodular functions.

1. Minimizing the difference between two submodular functions is not only NP hard, but also inapproximable.
2. Minimization/maximization of a submodular function subject to a submodular level set constraint (also known as submodular optimization subject to submodular cover or submodular knapsack constraint) admits bounded approximation guarantees.
3. Partitioning data based on a submodular function to maximize the average welfare is known as the submodular welfare problem, which also admits bounded approximation guarantees (see welfare maximization).

Submodular functions naturally occur in several real world applications, in economics, game theory, machine learning and computer vision. Owing to the diminishing returns property, submodular functions naturally model costs of items, since there is often a larger discount, with an increase in the items one buys. Submodular functions model notions of complexity, similarity and cooperation when they appear in minimization problems. In maximization problems, on the other hand, they model notions of diversity, information and coverage.

• Supermodular function
• Matroid, Polymatroid
• Utility functions on indivisible goods

{{reflist|30em|

refs=

{{cite journal |author-link=Martin Grötschel |first1=M. |last1=Grötschel |author-link2=László Lovász |first2=L. |last2=Lovasz |author-link3=Alexander Schrijver |first3=A. |last3=Schrijver |title=The ellipsoid method and its consequences in combinatorial optimization |journal=Combinatorica |volume=1 |issue=2 |year=1981 |pages=169–197 |doi=10.1007/BF02579273 |hdl=10068/182482 |s2cid=43787103 |hdl-access=free }}

{{cite journal |first=W. H. |last=Cunningham |title=On submodular function minimization |journal=Combinatorica |volume=5 |issue=3 |year=1985 |pages=185–192 |doi=10.1007/BF02579361 |s2cid=33192360 }}

{{cite journal |first1=S. |last1=Iwata |first2=L. |last2=Fleischer |first3=S. |last3=Fujishige |title=A combinatorial strongly polynomial algorithm for minimizing submodular functions |journal=J. ACM |volume=48 |year=2001 |issue=4 |pages=761–777 |doi=10.1145/502090.502096 |s2cid=888513 }}

{{cite journal |author-link=Alexander Schrijver |first=A. |last=Schrijver |title=A combinatorial algorithm minimizing submodular functions in strongly polynomial time |journal=J. Combin. Theory Ser. B |volume=80 |year=2000 |issue=2 |pages=346–355 |doi=10.1006/jctb.2000.1989 |url=https://ir.cwi.nl/pub/2108 |doi-access=free }}

R. Iyer, S. Jegelka and J. Bilmes, Fast Semidifferential based submodular function optimization, Proc. ICML (2013).

R. Iyer and J. Bilmes, Submodular Optimization Subject to Submodular Cover and Submodular Knapsack Constraints, In Advances of NIPS (2013).

R. Iyer and J. Bilmes, Algorithms for Approximate Minimization of the Difference between Submodular Functions, In Proc. UAI (2012).

M. Narasimhan and J. Bilmes, A submodular-supermodular procedure with applications to discriminative structure learning, In Proc. UAI (2005).

U. Feige, V. Mirrokni and J. Vondrák, Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), pp. 461–471.

{{cite journal|first1=George |last1=Nemhauser|author-link1=George Nemhauser|first2=L. A. |last2=Wolsey|first3=M. L. |last3=Fisher|title=An analysis of approximations for maximizing submodular set functions I|journal=Mathematical Programming |issue=14 |year=1978|volume=14 |pages=265–294|doi=10.1007/BF01588971 |s2cid=206800425 }}

G. Calinescu, C. Chekuri, M. Pál and J. Vondrák, Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comp. 40:6 (2011), 1740-1766.

N. Buchbinder, M. Feldman, J. Naor and R. Schwartz, A tight linear time (1/2)-approximation for unconstrained submodular maximization, Proc. of 53rd FOCS (2012), pp. 649-658.

Y. Filmus, J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, Proc. of 53rd FOCS (2012), pp. 659-668.

Z. Svitkina and L. Fleischer, Submodular approximation: Sampling-based algorithms and lower bounds, SIAM Journal on Computing (2011).

A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008

J. Bilmes, Submodularity in Machine Learning Applications, Tutorial at AAAI-2015.

H. Lin and J. Bilmes, A Class of Submodular Functions for Document Summarization, ACL-2011.

S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.

A. Krause and C. Guestrin, Near-optimal nonmyopic value of information in graphical models, UAI-2005.

M. Feldman, J. Naor and R. Schwartz, A unified continuous greedy algorithm for submodular maximization, Proc. of 52nd FOCS (2011).

{{cite book |author-link1=László Lovász |last1=Lovász |first1=L. |title=Mathematical Programming the State of the Art |chapter=Submodular functions and convexity |date=1983 |chapter-url= |pages=235–257 |doi=10.1007/978-3-642-68874-4_10 |isbn=978-3-642-68876-8 |s2cid=117358746 }}

{{cite encyclopedia |last1=Buchbinder |first1=Niv |last2=Feldman |first2=Moran |title=Submodular Functions Maximization Problems |encyclopedia= Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications |year=2018 |editor1-last=Gonzalez |editor1-first=Teofilo F. |publisher=Chapman and Hall/CRC |doi=10.1201/9781351236423 |isbn=9781351236423 |url=https://www.taylorfrancis.com/chapters/edit/10.1201/9781351236423-42/submodular-functions-maximization-problems-niv-buchbinder-moran-feldman|url-access=subscription }}

{{Cite web|last=Vondrák|first=Jan|title=Polyhedral techniques in combinatorial optimization: Lecture 17|url=https://theory.stanford.edu/~jvondrak/CS369P/lec17.pdf}}

}}

• {{Citation|last=Schrijver|first=Alexander|author-link=Alexander Schrijver|year=2003|title=Combinatorial Optimization|publisher=Springer|isbn=3-540-44389-4}}
• {{Citation|last=Lee|first=Jon|author-link=Jon Lee (mathematician)|year= 2004 |title=A First Course in Combinatorial Optimization |publisher=Cambridge University Press|isbn= 0-521-01012-8}}
• {{Citation|last=Fujishige|first=Satoru|year=2005|title=Submodular Functions and Optimization|publisher=Elsevier|isbn=0-444-52086-4}}
• {{Citation|last=Narayanan|first=H.|year= 1997 |title=Submodular Functions and Electrical Networks|publisher=Elsevier |isbn= 0-444-82523-1}}
• {{citation | last=Oxley | first=James G. | title=Matroid theory | series=Oxford Science Publications | location=Oxford | publisher=Oxford University Press | year=1992 | isbn=0-19-853563-5 | zbl=0784.05002 }}

• http://www.cs.berkeley.edu/~stefje/references.html has a longer bibliography
• http://submodularity.org/ includes further material on the subject

Matroid theory