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

• Approximation algorithm for an optimization problem finds an answer at most $\alpha$ times worse than the optimal one. What does an approximation algorithm for a problem which only returns true or false do? Do you want that $\alpha$ to turn into probability? – Karolis Juodelė Jan 1 '14 at 13:32
• @KarolisJuodelė that's what I had in mind - create an algorithm that returns the correct answer with a provably high probability. Is this possible in general? – Erel Segal-Halevi Jan 1 '14 at 14:21
• @ErelSegalHalevi That seems impossible as long as you don't know anything about the distribution of the result within the error interval of the approximation algorithm. – Raphael Feb 19 '15 at 8:21

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$).