Coverage function ($F(S)=|{\bigcup }_{v\in S}{C}_v|$)

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.

A weighted coverage function assigns nonnegative weights $w_u$ to members of a finite universe $U$, lets each choice $i$ cover a subset $A_i\subseteq U$, and values a selection $S$ byAn item covered twice is counted only once. If $A_1=\{a,b\}$, $A_2=\{b,c\}$ and the weights are $2,3,5$, then $f(\{1\})=5$, $f(\{2\})=8$ and $f(\{1,2\})=10$.

Its marginal gain of a set function is the total weight of newly covered items. As the selected set grows, fewer uncovered items remain, so the marginal gain of a set function can only decrease. This proves that a weighted coverage function is a monotone submodular set function. Nonnegative weights are essential to this argument. The construction models selecting sensors or experiments whose observations overlap.^[ref]