The problem can be formulated as:

$\min f(\textbf{x})=\sum_{i=1}^{n} \prod_{j \in N(i)}(1-F(x_i))$ s.t. $\sum_{i=1}^n x_i \leq B$

$N(i)$ is a set of i. And $F_{x_i}$ can be any function with range between [0,1].

if $F(x_i)$ is a convex function and $\prod_{j \in N(i)}(1-x_i)$ is concave, the objective function is a concave function.

Is this an NP-hard problem? Is there any possible ways so that I can get the approximation?

  • 1
    $\begingroup$ You should look at "convex programming". Optimization over convex (or concave) functions is usually easier because local minima are also global minima. I don't understand your objective function though. What is the $j$ indexing the product? $\endgroup$ – Wandering Logic Aug 30 '13 at 11:40
  • $\begingroup$ As "convex optimization" is usually about minimizing a convex function, and might not be applicable here. $\endgroup$ – Godot Aug 30 '13 at 13:46
  • 1
    $\begingroup$ A concave function is the negative of a convex function, so $\max -f(x)$ is a convex optimization problem. $\endgroup$ – Wandering Logic Aug 30 '13 at 18:17
  • $\begingroup$ The standard form of convex optimization is minimizing a convex function, but here it is maximizing a convex funcion $\endgroup$ – Godot Aug 31 '13 at 2:23
  • $\begingroup$ Note that "can be formulated as" implies that you can only get upper bounds on the complexity of the original problem, not lower bounds. There may be another representation that opens up more efficient approaches. Meaning, you should explain what "the problem" is. $\endgroup$ – Raphael Sep 2 '13 at 9:48

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.