Approximation algorithms for NP-complete problems

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

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.

StackExchange Computer Science Q#19050, answer score: 6