Lemma C.3 (Lemma 2.2 [1]}) 

Let \(f\,:\,2^E \rightarrow \mathbb {R}_+\)  be a submodular function. Further, let \(R\)  be a random subset of \(T\subseteq E\)  in which every element occurs with probability at most \(p\)  (not necessarily independently). Then, \(\mathbf {E}f(R) \ge (1 - p)f(\emptyset )\) .

