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?