Maximizing difference of a submodular and a modular function I'm considering a network planning problem which is stated as follows:
From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that 
\begin{equation}
f(\mathcal{A}) - \sum_{v_i \in \mathcal{A}} c_i
\end{equation}
is maximized where $f$ is a monotone submodular function and $c_i \ge 0$ is the cost of selecting $v_i$. The problem is an instance of nonomonotone submodular maximization for which a local search heuristic with approximation bound of $\frac{2}{5} - \frac{\epsilon}{n}$ is presented in

Uriel Feige, Vahab S. Mirrokni, Jan Vondrák: "Maximizing Non-Monotone Submodular Functions ", FOCS 2007.

I'm wondering if anyone is aware of a better approximation algorithm for my specific problem?
To simplify life, let $\mathcal V = [n] := \{1,2,\ldots,n\}$. For $A \subseteq [n]$, define $h(A):=\sum_{i \in A}c_i$. Note that $h$ defines a modular (i.e additive) set function. Now, suppose there exists $\gamma \in [0, 1]$ such that $f$ is weakly $\gamma$-submodular, i.e such that

$$
\sum_{i \in B\setminus A}f(A \cup \{i\}) - f(A)  \ge \gamma (f(A \cup B) - f(A)),\;\forall A,B \subseteq [n].
$$

Then, greedy maximization produces a subset $A^G$  with $k$ elements such that

$$
f(A^G)-h(A^G) \ge (1-e^{-\gamma})f(A^*)-h(A^*),
$$

where $A^*$ is the $k$-element subset of $[n]$ which maximizes $f(A)-h(A)$.
This is a direct consequence of Theorem 3 of this ICML paper.