= Exact-cover inequality for submodular set functions
{title2=$\sum_{i=1}^t f(T_i)\geq kf(T)$}
Suppose $f$ is a <normalised set function> and a <submodular set function>, and $T_1,\ldots,T_t\subseteq T$ cover every element of $T$ exactly $k$ times, counting repetitions in the indexed collection. Then the displayed inequality holds. Neither the <monotone set function> property nor the <nonnegative function> property is required.
\b[Proof.] Fix an ordering of $T$ and write $a_j=f(P_j)-f(P_{j-1})$ for its successive <marginal increments>. The <chain lower bound for a submodular set function> gives $f(T_i)\geq\sum_{x_j\in T_i}a_j$. Summing counts each $a_j$ exactly $k$ times, and $\sum_ja_j=f(T)$. Exact coverage matters because the $a_j$ may be negative. For a <monotone set function>, the same argument also allows each element to occur at least $k$ times.
Back to article page
