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

Your Answer

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

Browse other questions tagged or ask your own question.