In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the distance of solutions from optimal is preserved to some degree.
However, unlike with other reductions, approximation-preserving reductions often overlap in what properties they demonstrate on optimization problems (e.g. complexity class membership or completeness, or inapproximability).
Not all types of approximation-preserving reductions can be used to show membership in all approximability complexity classes, the most notable of which are PTAS and APX.
Some reductions shown below only preserve membership in APX or PTAS, but not the other.
Because of this, careful choice must be made when selecting an approximation-preserving reductions, especially for the purpose of proving completeness of a problem within a complexity class.
In a strict reduction, the approximation ratio of a solution y' to an instance x' of a problem B must be at most as good as the approximation ratio of the corresponding solution y to instance x of problem A.
Strict reduction preserves membership in both PTAS and APX.
S-reduction is a very special case of strict reduction, and is even more constraining.
L-reductions preserve membership in PTAS as well as APX (but only for minimization problems in the case of the latter).
PTAS-reductions are a generalization of P-reductions, shown below, with the only difference being that the function g is allowed to depend on the approximation ratio r. A-reduction and P-reduction are similar reduction schemes that can be used to show membership in APX and PTAS respectively.
Both introduce a new function c, defined on numbers greater than 1, which must be computable.
E-reduction, which is a generalization of strict reduction but implies both A-reduction and P-reduction, is an example of a less restrictive reduction style that preserves membership not only in PTAS and APX, but also the larger classes Log-APX and Poly-APX.
AP-reductions are used to define completeness in the classes Log-APX and Poly-APX.
They are a special case of PTAS reduction, meeting the following restrictions.
, with the additional generalization that the function g is allowed to depend on the approximation ratio r, as in PTAS-reduction.
An additional restriction actually needs to be imposed for AP-reduction to preserve Log-APX and Poly-APX membership, as E-reduction does: for fixed problem size, the computation time of f, g must be non-increasing as the approximation ratio increases.