# 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 $$f(\mathcal{A}) - \sum_{v_i \in \mathcal{A}} c_i$$ 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?

• The result of Feige, Mirrokni and Vondrak applies only to non-negative functions. Your function is no guaranteed to be non-negative unless you are making additional assumptions. I guess you meant the approximation in FMS is 2/5, not 2/4. There is an upcoming paper in FOCS 2012 by Buchbinder etal who obtain an optimal 1/2 approximation for non-negative submodular function maximization. Without non-negativity the problem is inapproximable. See the following paper for some related work on your problem. dl.acm.org/citation.cfm?id=1616497.1616507 – Chandra Chekuri Aug 26 '12 at 23:40
• Thanks Chandra for your very helpful comment. You were right about the bound. It has been edited. – Ali Aug 27 '12 at 19:52

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.