Following the pioneering work of Das and Kempe [1]}, there has been a vast literature on other notions of approximate submodularity. Horel and Singer [2]} define a function \(F\)  as \(\varepsilon \) -approximately submodular if \(F\)  is within a \((1+\varepsilon )\)  multiplicative factor of some submodular function \(f\)  and investigate the relationship between \(\varepsilon \)  and the number of queries needed to optimize it. Chierichetti et al. [3]} focus on \(\varepsilon \) -additive approximate submodular function. As noted in their work, their definition is incomparable with the notion of weak submodularity based on submodularity ratio. Gong et al. [4]} and Nong [5]} use a generic submodularity ratio \(\gamma _{\textrm {gen}}\)  and design algorithms to maximize submodular functions when \(\gamma _{\textrm {gen}}\)  is bounded. Specifically, Gong et al. [4]} obtained a \((1-e^{-1})(1-e^{-\gamma _{\textrm {gen}}})\)  approximation under a matroid constraint.A set function has generic submodularity ratio \(\gamma _{\textrm {gen}}\)  if \(f(e \mid A) \ge \gamma _{\textrm {gen}}\cdot f(e \mid B)\)  for all \(A \subseteq B\)  and \(e \in X \backslash B\) . We note that that the definition is more restrictive than ours, i.e., \(\gamma \ge \gamma _{\textrm {gen}}\) . In particular, for the subset selection problem, it is easy to formulate instances for which \(\gamma _{\textrm {gen}}= 0\)  and so the generic ratio provides no approximation guarantee, but \(\gamma > 0\) .
All the definitions introduced here assume that the objective is monotone. Recently Santiago and Yoshida have proposed a notion of approximate submodularity that extends to the non-monotone case [7]}.
