= Submodular set function
{title2=$f(A)+f(B)\geq f(A\cup B)+f(A\cap B)$}
{wiki}
= Submodularity
{synonym}
A <set function> $f:\mathcal P(V)\to\mathbb R$ is submodular when
$$
f(A)+f(B)\geq f(A\cup B)+f(A\cap B)
$$
for every $A,B\subseteq V$. For finite $V$, this is equivalent to <diminishing returns>:
$$
\Delta_x f(A)\geq\Delta_x f(B)\qquad(A\subseteq B,\ x\notin B).
$$
The <marginal increment> of an element can only decrease as the surrounding <set> grows.<Learning with Submodular Functions: A Convex Optimization Perspective by Francis Bach>[§2.2, Proposition 2.2: equivalent first-difference condition on the finite ground set]{ref}
For necessity, apply the defining <inequality> to $A\cup\{x\}$ and $B$. Conversely, enumerate $A\setminus B$ and compare adding its elements to $A\cap B$ with adding them to $B$. Summing the marginal inequalities gives $f(A)-f(A\cap B)\geq f(A\cup B)-f(B)$.
A <coverage function> is an example: $f(S)=|\bigcup_{v\in S}C_v|$ counts the covered objects in a finite universe. An added $C_x$ contributes only objects not already covered, so its gain decreases with $S$. <Entropy submodularity> is another fundamental example.
Back to article page