Weighted coverage function

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]