2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ – Karolis Juodelė Jan 1 '14 at 13:32
  • 1
    $\begingroup$ @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? $\endgroup$ – Erel Segal-Halevi Jan 1 '14 at 14:21
  • $\begingroup$ @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. $\endgroup$ – Raphael♦ Feb 19 '15 at 8:21
4
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.