Using approximations to optimization problems for threshold problems Many problems in computer science come in two flavors:


Optimization problem: "Find an object with the largest size".
Decision problem: "Given $n$, find an object with a size of at least $n$, or reply that such an object does not exist".


Given a solver for the optimization problem, the decision problem can be solved simply by checking if the optimal solution has a size of at least $n$. But this doesn't help if the optimization problem is NP-hard.

MY QUESTION IS: If we have a constant-factor approximation algorithm for the optimization problem, how can we use it for the threshold problem?

A possible way is: if the approximate solution has a size of at least $n$, return it; if it has a size of less than $n/c$ (where c is the approximation constant), return that an object of size $n$ does not exist; otherwise, return "I don't know".  This may return a correct answer in many cases, but not in all cases.

Is there a better way?
First off, a technicality: optimization problems aren't NP-complete; only decision problems can be NP-complete (or in NP).  Thus, it's only the decision problem (what you call the "threshold problem") that is in NP, or NP-complete.

On to the substance of your question.  The answer is: You can't.  In general, the approximation algorithm typically doesn't let you solve the decision problem.  Think about it.  We have many problems for where the decision problem is NP-complete, but where we have a polytime approximation algorithm.  If the approximation algorithm let us quickly solve the decision problem (or the corresponding optimization problem), then we'd immediately have a polytime solution to a NP-complete (or NP-hard) problem, and thus a proof that P=NP.  When you start with some assumption and it leads to a conclusion that is too good to be true, that's a sign that the assumption probably wasn't valid.

No, your "obvious answer" doesn't work.  Decision problems aren't allowed to return "I don't know".  No, there isn't a better way (assuming the problem is NP-hard, and assuming $P\ne NP$).