There are many different types of approximation-preserving reductions, all of which have a different guarantee (the third point in the definition above). 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). The different types of reductions are used instead as varying reduction techniques, in that the applicable reduction which is most easily adapted to the problem is used. 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. A reduction below
preserves membership in a complexity class C if, given a problem A that reduces to problem B via the reduction scheme, and B is in C, then A is in C as well. 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. Crescenzi suggests that the three most ideal styles of reduction, for both ease of use and proving power, are PTAS reduction, AP reduction, and L-reduction. The reduction descriptions that follow are from Crescenzi's survey of approximation-preserving reductions.
Strict reduction Strict reduction is the simplest type of approximation-preserving reduction. 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. In other words: : R_A(x, y) \le R_B(x', y') for x' = f(x), y = g(y'). Strict reduction is the most straightforward: if a strict reduction from problem A to problem B exists, then problem A can always be approximated to at least as good a ratio as problem B. Strict reduction preserves membership in both PTAS and APX. There exists a similar concept of an
S-reduction, for which c_A(x, y) = c_B(x', y'), and the optima of the two corresponding instances must have the same cost as well. S-reduction is a very special case of strict reduction, and is even more constraining. In effect, the two problems A and B must be in near-perfect correspondence with each other. The existence of an S-reduction implies not only the existence of a strict reduction but every other reduction listed here.
L-reduction L-reductions preserve membership in PTAS as well as APX (but
only for minimization problems in the case of the latter). As a result, they cannot be used in general to prove completeness results about APX, Log-APX, or Poly-APX, but nevertheless they are valued for their natural formulation and ease of use in proofs.
PTAS-reduction PTAS-reduction is another commonly used reduction scheme. Though it preserves membership in PTAS, it does not do so for APX. Nevertheless, APX-completeness is defined in terms of PTAS reductions. PTAS-reductions are a generalization of P-reductions, shown below, with the only difference being that the function is allowed to depend on the approximation ratio .
A-reduction and P-reduction 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 , defined on numbers greater than 1, which must be computable. In an A-reduction, we have that :R_B(x', y') \le r \rightarrow R_A(x, y) \le c(r). In a P-reduction, we have that :R_B(x', y') \le c(r) \rightarrow R_A(x, y) \le r. The existence of a P-reduction implies the existence of a PTAS-reduction.
E-reduction 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. E-reduction introduces two new parameters, a polynomial and a constant \beta. Its definition is as follows. In an E-reduction, we have that for some polynomial and constant \beta, • c_B(\text{OPT}_B(x')) \le p(|x|) c_A(\text{OPT}_A(x)), where |x| denotes the size of the problem instance's description. • For any solution y' to , we have R_A(x, y) \le 1 + \beta \cdot (R_B(x', y') - 1). To obtain an A-reduction from an E-reduction, let c(r) = 1+\beta \cdot (r-1), and to obtain a P-reduction from an E-reduction, let c(r) = 1 + (r-1)/\beta.
AP-reduction 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. In an AP-reduction, we have that for some constant \alpha, : R_B(x', y') \le r \rightarrow R_A(x, y) \le 1 + \alpha \cdot (r-1) with the additional generalization that the function is allowed to depend on the approximation ratio , as in PTAS-reduction. AP-reduction is also a generalization of E-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 must be non-increasing as the approximation ratio increases.
Gap reduction A gap reduction is a type of reduction that, while useful in proving some inapproximability results, does not resemble the other reductions shown here. Gap reductions deal with optimization problems within a decision problem container, generated by changing the problem goal to distinguishing between the optimal solution and solutions some multiplicative factor worse than the optimum. == See also ==