A submodular function \(f:2^{X} \rightarrow \mathbb {R}\)  is a set function such that \(f(e | A ) \ge f(e | B)\)  for all \(A \subseteq B \subseteq X, e \in X \backslash B\)  and where \(f(e | S ) := f(S \cup \lbrace e\rbrace ) - f(S)\)  denotes the marginal contribution of element \(e\)  with respect to some set \(S\) .
Submodularity has long played a central role in combinatorial optimization and operational research, because it provides a discrete analogue of convexity and also captures a natural diminishing return property. More recently, a wide range of applications have also been found in data science and machine learning. Here, optimization of submodular functions has been used as a general technique for subset selection problems [1]}, [2]}, [3]}, sensor placement [3]}, document summarization [5]}, [6]}, [7]}, and influence maximization in social networks [8]}.
