= Maximum of element weights
{title2=$f(S)=\max_{v\in S}w(v)$}
Let $V$ be a nonempty <finite set> with real weights $w(v)$. For nonempty <subsets> put $f(S)=\max_{v\in S}w(v)$ and choose $f(\varnothing)=c\leq\min_{v\in V}w(v)$. This defines a <monotone set function> and a <submodular set function> on the full <power set>.
To check <diminishing returns>, for $x\notin S$ the <marginal increment> is $\Delta_x f(S)=\max\{0,w(x)-f(S)\}$. If $A\subseteq B$, then $f(A)\leq f(B)$, so $\Delta_x f(A)\geq\Delta_x f(B)$. Choosing the value of the <empty set> no larger than every weight makes this calculation valid even for $A=\varnothing$.
For weights $2,5,9$ and $c=0$, adding the weight-$5$ element to a weight-$2$ selection increases $f$ by $3$; adding it to a selection already containing weight $9$ increases $f$ by zero.
Back to article page
