Maximizing a monotone submodular function with a cardinality constraint can be solved by using a simple greedy heuristic. However, if the submodular function is non-monotone, the greedy heuristic can perform arbitrarily poorly.
Now I have a very special non-monotone submodular function: $$G(S)=F(S)−a|S|,\qquad S\subseteq V$$ where $F(S)$ is monontone submodular, $a$ is a constant. Furthermore, $G(S)≥0,G(\emptyset)=G(V)=0$.
Does the greedy heuristic still perform poorly for problem $\max_{|S|\leq K}G(S)$?
