L-reduction

From Wikipedia, the free encyclopedia

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.

[edit] Definition

Let A and B be optimization problems and cA and cB 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
|OPT(x)-c_A(S(y))| \le \beta |OPT(R(x))-c_B(y)|

[edit] 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.

[edit] See also

Languages