6
$\begingroup$

Given two NP NP-hard functional problems, A and B, one can find a reduction of A to B. Is it possible to find a reduction that would honour approximations? That is, if you have an approximation algorithm for B that yield approximate solutions within accuracy $\delta$, is it possible to reduce A to B in such a way that one would be able to derive an approximate solution of A within accuracy $\epsilon = \epsilon(\delta)$?

$\endgroup$
  • 1
    $\begingroup$ I'll leave a proper answer to experts, but let me point you towards the notion of strong np-completeness. $\endgroup$ – Raphael Dec 16 '13 at 20:07
  • 1
    $\begingroup$ In certain circumstances an approximation-preserving reduction is possible. These instances are characterized by L-reductions. However, as @Raphael, noted, not all problems possess this feature. $\endgroup$ – Nicholas Mancuso Dec 17 '13 at 17:05
5
$\begingroup$

It depends on the problems. Some NP-complete problems are in APX (can be approximated to some constant amount) and some are not. This shows that you cannot in general assume the existence of a transformation such as the one you mention; this is spelled out here.

A concept somewhat similar to what you mention is APX-hardness. First, some definitions. APX, as mentioned, is the class of problems approximable to some constant in polytime. PTAS is the class of problems which can be approximated arbitrarily well in polytime. A problem is APX-hard if there is a "PTAS reduction" (approximation-preserving reduction) from every problem in APX to that problem. One problem which is APX-hard is MAX-SAT.

A related definition is MaxSNP. This is a class of graph problems with the following property: there is a PTAS reduction from every problem in APX to some problem in MaxSNP.

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