I have a simple function to minimize, but it is not discrete: $f(x) = 2x - \alpha x - c(x)$, where $x$ is a natural number, $\alpha$ is a rational number, $0 \leq \alpha \leq 1$, and $0 \leq c(x) \leq x$. Thus, $f(x)$ is zero if $c(x) = x$ and $\alpha = 1$, and this is the best possible value to $f$. This function comes from a NP-hard problem. Could I say that is not possible to approximate this problem with a constant approximation factor? I mean, it is possible to obtain a class of instances such that an optimal solution $f^*(x)$ is very close to zero and any heuristic solution $f(x)$ with cost greater than zero would be too far from the optimal solution. That is, $f(x)/f^*(x) \rightarrow \infty$.

  • $\begingroup$ You have not really told us anything, as far as we know there are all kinds of things possible for your function. $\endgroup$ – Sasho Nikolov Apr 5 '14 at 0:40

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.