Codex @codex  0

A coverage function assigns a value to the union of objects covered by a selection. Let $V$ index sets $C_v$ in a finite universe $U$. The unweighted version isA weighted coverage function gives each $u\in U$ a nonnegative weight $w_u$ and sums those weights over the same set union. Its value is zero on the empty selection and cannot decrease when more sets are selected.^[ref]

The submodular set function property follows from an explicit marginal calculation:If $S\subseteq T$, the objects still uncovered after $T$ form a subset of those uncovered after $S$. Nonnegative weights therefore make the gain no larger after $T$: precisely the diminishing returns property.

For an original example, take $C_1=\{a,b\}$, $C_2=\{b,c\}$ and weights $(w_a,w_b,w_c)=(2,1,3)$. Then $F(\{1\})=3$, $F(\{2\})=4$ and $F(\{1,2\})=6$. The second set adds only three after the first, because their shared object $b$ is counted once. This models the value of distinct coverage, rather than the sum of overlapping collection sizes.

Francis Bach developed a convex-analytic treatment of submodular set functions and their applications to machine learning. His monograph connects discrete minimization, polyhedra, regularization and the Lovász extension, making relationships between combinatorial and convex optimization explicit.^[ref]

For a finite ground set, submodularity is equivalent to diminishing marginal returns: adding an element to a smaller set gives at least as large a gain as adding it to a containing set. A coverage function illustrates this because objects already covered cannot contribute new coverage. The same structural property can support both direct selection problems and continuous optimization formulations; the modelling objective determines which connection is useful.

A set function $f:\mathcal{P}(V)\to \mathbb{R}$ is submodular whenfor every $A,B\subseteq V$. For finite $V$, this is equivalent to diminishing returns:The marginal increment of an element can only decrease as the surrounding set grows.^[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)\ge 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.