= 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$ by
$$
f(S)=\sum_{u\in\bigcup_{i\in S}A_i}w_u.
$$
An 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.<Learning with Submodular Functions: A Convex Optimization Perspective by Francis Bach>[Section 6.3, set covers]{ref}
Back to article page
