Maximizing a general monotone submodular function $f$ under the constraint that $|S|\leq k$, can be approximated to $(1-1/e)$.  I am wondering if a better approximation algorithm exists if the function $f$ has these additional properties for any element $x$ and subset $S$:$f(\{x\}) \in \{0, 1, 2\}$$f(S \cup \{x\}) - f(S) \in \{0, 1, 2\}$or even the more restricted properties : $f(\{x\}) \in \{0, 1\}$$f(S \cup \{x\}) - f(S) \in \{0, 1\}$
Maximizing a submodular function with restricted values
approximation algorithms;submodularity