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?