6
$\begingroup$

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?

$\endgroup$
2
  • 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$ Aug 26, 2012 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, 2012 at 19:52

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ Welcome to Theoretical Computer Science! While this link may answer the question, it is better 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. $\endgroup$
    – Glorfindel
    Feb 7 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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