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, for any $ S,T\subseteq E : f(T)\leq f(S) + \sum_{e_i\in T-S}(f(S\cup\{e_i\})-f(S)) $ where $f$ is a submodular monotone function . I've tried induction but got no where.