1
$\begingroup$

We talked about the following theorem in class but I am still having problems to understand it:

For a NP-complete decision problem "Does a valid solution with a value $\leq K$ exist?" there is no approximation algorithm for the corresponding minimization problem with an approximation factor $\lt 1 + 1/K$.

Why is this necessarily true? And where does that upper bound $1 + 1/K$ come from?

$\endgroup$
1
$\begingroup$

The crucial assumption here is that the value is an integer.

If the value is an integer, then telling whether there is a valid solution with value $\le 10$ is as hard as telling whether there is a valid solution with value $\le 10.999$ (it's the question). Thus, you shouldn't expect a polynomial-time approximation algorithm with approximation factor $10.999/10$ or better -- if you had such an approximation algorithm, you could tell whether there was a valid solution with value $\le 10.999$, which would tell you whether there is a valid solution with value $\le 10$, which would let you solve the original problem, which would mean that you have found a polynomial-time algorithm for a NP-complete problem. That would be unexpected.

$\endgroup$

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.