A set function f on the subsets of a set E is called submodular if it satisfies a natural diminishing returns property: for any two subsets S \subseteq T \subseteq E and an element x outside T, we have f(T + x) - f(T) \leq f(S+x)