In mathematics, a submodular set function (also known as a submodular function) is a set function that, informally, describes the relationship between a set of inputs and an output, where adding more of one input has a decreasing additional benefit (diminishing returns). The natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory (as functions modeling user preferences) and electrical networks. Recently, submodular functions have also found utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains.

If ${\displaystyle \Omega }$ is a finite set, a submodular function is a set function ${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$, where ${\displaystyle 2^{\Omega }}$ denotes the power set of ${\displaystyle \Omega }$, which satisfies one of the following equivalent conditions.

A nonnegative submodular function is also a subadditive function, but a subadditive function need not be submodular. If ${\displaystyle \Omega }$ is not assumed finite, then the above conditions are not equivalent. In particular a function ${\displaystyle f}$ defined by ${\displaystyle f(S)=1}$ if ${\displaystyle S}$ is finite and ${\displaystyle f(S)=0}$ if ${\displaystyle S}$ is infinite satisfies the first condition above, but the second condition fails when ${\displaystyle S}$ and ${\displaystyle T}$ are infinite sets with finite intersection.

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

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 ${\displaystyle f}$ is non-monotone if there are sets ${\displaystyle S,T}$ in its domain s.t. ${\displaystyle S\subset T}$ and ${\displaystyle f(S)>f(T)}$.

A non-monotone submodular function ${\displaystyle f}$ is called symmetric if for every ${\displaystyle S\subseteq \Omega }$ we have that ${\displaystyle f(S)=f(\Omega -S)}$. Examples of symmetric non-monotone submodular functions include:

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

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.