Maximizing difference of a submodular and a modular function

Question

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?

Answer 1

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.

Answer 2

See recent work Unconstrained Submodular Maximization with Modular Costs: Tight Approximation and Application to Profit Maximization. It provides both lower and upper bound for your problem. It seems that from Theorem 1 and 2, their algorithm is optimal!