<p>To simplify life, let <span class="math-container">$\mathcal V = [n] := \{1,2,\ldots,n\}$</span>. For <span class="math-container">$A \subseteq [n]$</span>, define <span class="math-container">$h(A):=\sum_{i \in A}c_i$</span>. Note that <span class="math-container">$h$</span> defines a modular (i.e additive) set function. Now, suppose there exists <span class="math-container">$\gamma \in [0, 1]$</span> such that <span class="math-container">$f$</span> is weakly <span class="math-container">$\gamma$</span>-submodular, i.e such that</p>

<p><span class="math-container">$$
\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].
$$</span></p>

<p>Then, greedy maximization produces a subset <span class="math-container">$A^G$</span>  with <span class="math-container">$k$</span> elements such that</p>

<p><span class="math-container">$$
f(A^G)-h(A^G) \ge (1-e^{-\gamma})f(A^*)-h(A^*),
$$</span></p>

<p>where <span class="math-container">$A^*$</span> is the <span class="math-container">$k$</span>-element subset of <span class="math-container">$[n]$</span> which maximizes <span class="math-container">$f(A)-h(A)$</span>.
This is a direct consequence of <a href="http://proceedings.mlr.press/v97/harshaw19a/harshaw19a-supp.pdf" rel="nofollow noreferrer">Theorem 3 of this ICML paper</a>.</p>

CC BY-SA 4.0
2020-05-20T14:47:26.570Z
See also  more recent paper. https://arxiv.org/abs/2002.07782
Chandra Chekuri
CC BY-SA 4.0
2020-05-18T23:01:42.440Z
2020-05-18T23:01:42.440Z
dohmatob
<p>See recent work <a href="http://vldb.org/pvldb/vol14/p1756-jin.pdf" rel="nofollow noreferrer">Unconstrained Submodular Maximization with Modular Costs:
Tight Approximation and Application to Profit Maximization.
</a> It provides both lower and upper bound for your problem. It seems that from Theorem 1 and 2, their algorithm is optimal!</p>

CC BY-SA 4.0
2023-02-07T19:26:57.320Z
Welcome to Theoretical Computer Science! While this link may answer the question, it [is better](//meta.stackexchange.com/a/8259/295232) to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes or disappears.
Glorfindel
CC BY-SA 4.0
2023-02-07T18:32:40.587Z
2023-02-07T18:32:40.587Z
XLTY
<p>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</p>

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

<p>I'm wondering if anyone is aware of a better approximation algorithm for my specific problem?</p>

CC BY-SA 3.0
2012-08-26T23:40:18.333Z
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. http://dl.acm.org/citation.cfm?id=1616497.1616507
Chandra Chekuri
CC BY-SA 3.0
2012-08-27T19:52:52.783Z
Thanks Chandra for your very helpful comment. You were right about the bound. It has been edited.
Ali
<ds.algorithms><approximation-algorithms><optimization><submodularity>
Maximizing difference of a submodular and a modular function
Ali
# Maximizing difference of a submodular and a modular function

(Asked by: username_0 on 2012-08-23)

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?

**Tags:** ds.algorithms, approximation-algorithms, optimization, submodularity

> **Comments:**
> **username_1**: 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. http://dl.acm.org/citation.cfm?id=1616497.1616507  
> **username_0**: Thanks Chandra for your very helpful comment. You were right about the bound. It has been edited.  

---

## 2 answers

### Answer by username_2 on 2020-05-18. Score: 2

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](http://proceedings.mlr.press/v97/harshaw19a/harshaw19a-supp.pdf).

> **Comments:**
> **username_1**: See also  more recent paper. https://arxiv.org/abs/2002.07782  

---

### Answer by username_3 on 2023-02-07. Score: 0

See recent work [Unconstrained Submodular Maximization with Modular Costs:
Tight Approximation and Application to Profit Maximization.](http://vldb.org/pvldb/vol14/p1756-jin.pdf) It provides both lower and upper bound for your problem. It seems that from Theorem 1 and 2, their algorithm is optimal!

> **Comments:**
> **username_4**: Welcome to Theoretical Computer Science! While this link may answer the question, it [is better](//meta.stackexchange.com/a/8259/295232) to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes or disappears.  

---

