 Coverage function

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.