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?

  • 5
    $\begingroup$ 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 $\endgroup$ – Chandra Chekuri Aug 26 '12 at 23:40
  • $\begingroup$ Thanks Chandra for your very helpful comment. You were right about the bound. It has been edited. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.