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?
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.
