Owing to their simplicity, both greedy and local search algorithms are also often used as heuristics in practice, even for functions that are not submodular. One such setting is subset selection via forward regression. Here the goal is to select a small set of variables that together “best” predict some target quantity. The forward regression algorithm selects these variables in a greedy, stepwise fashion. In this setting, Das and Kempe [1]} showed that the squared multiple correlation objective function, also know as the \(R^2\)  objective, is submodular if suppressors are not present among the predictor variables, thus justifying the use of the greedy algorithm. In later work [2]} they showed that even in the presence of suppressors, a weaker property (appropriately) deemed weak submodularity often holds. They introduced the submodularity ratio \(\gamma \) , which measures how far a function deviates from submodularity when considering the effect of adding individual elements. Their definition is directly motivated by the greedy algorithm for a cardinality constraint, for which they derive an approximation guarantee of \((1 - e^{-\gamma })\) . This guarantee, which depends on the objective function's submodularity ratio \(\gamma \in [0,1]\) , applies even for functions that are not submodular. This result has been shown to be tight in the value oracle model [3]}.
