A few definitions:
A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions:
- for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $
- for every $ S,T\subseteq E $ with $ S\subseteq T $ and for every $ x\in E\setminus T : f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T) $
A monotone submodular function is a submodular functions such that for every $ S,T \subseteq E $ with $ S\subseteq T : f(T)\geq f(S) $ . We also define $ f(\emptyset) = 0 $.
Show that $ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) $ where $ e_i\in S $ for all i, where f is a monotone submodular function.