L-reduction

L-reduction is a transformation of optimization problems which keeps the approximability features. L-reductions in studies of approximability of optimization problems play a similar role to that of polynomial reductions in the studies of computational complexity of decision problems.

The term "L reduction" is sometimes used to refer to log-space reductions, by analogy with the complexity class L, but this is a different concept.

Definition

Let A and B be optimization problems and c_A and c_B their respective cost functions. A pair of functions R and S is an L-reduction if all of the following conditions are met:
* functions R and S are computable in logarithmic amount of space,
* if x is an instance of problem A, then R(x) is an instance of problem B,
* if y is a solution to R(x), then S(y) is a solution to x,
* there exists such positive constant α that:$OPT(R(x))\; le\; alpha\; OPT(x)$
* there exists such positive constant β that:

Properties

It can be shown that if (R,S) is an L-reduction of problem A to B with constants α and β (see above) and there exists a polynomial ε-approximation algorithm for B then there also exists a polynomial δ-approximation algorithm for A where:This also implies that if B has a polynomial-time approximation scheme then so does A.

ee also

* Approximation algorithm,
* NP-complete,
* MAXSNP.