Neha Patil (Editor)

L reduction

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In computer science, particularly the study of approximation algorithms, an L-reduction ("linear reduction") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preserving reduction. 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.

Contents

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 cA and cB their respective cost functions. A pair of functions f and g is an L-reduction if all of the following conditions are met:

  • functions f and g are computable in polynomial time,
  • if x is an instance of problem A, then f(x) is an instance of problem B,
  • if y' is a solution to f(x), then g(y' ) is a solution to x,
  • there exists a positive constant α such that
    • O P T B ( f ( x ) ) ≤ α O P T A ( x ) ,
  • there exists a positive constant β such that for every solution y' to f(x)
    • | O P T A ( x ) − c A ( g ( y ′ ) ) | ≤ β | O P T B ( f ( x ) ) − c B ( y ′ ) | .

    Implication of PTAS reduction

    An L-reduction from problem A to problem B implies an AP-reduction when A and B are minimization problems and a PTAS reduction when A and B are maximization problems. In both cases, when B has a PTAS and there is a L-reduction from A to B, then A also has a PTAS. This enables the use of L-reduction as a replacement for showing the existence of a PTAS-reduction; Crescenzi has suggested that the more natural formulation of L-reduction is actually more useful in many cases due to ease of usage.

    Proof (minimization case)

    Let the approximation ratio of B be 1 + δ . Begin with the approximation ratio of A, c A ( y ) O P T A ( x ) . We can remove absolute values around the third condition of the L-reduction definition since we know A and B are minimization problems. Substitute that condition to obtain

    c A ( y ) O P T A ( x ) ≤ O P T A ( x ) + β ( c B ( y ′ ) − O P T B ( x ′ ) ) O P T A ( x )

    Simplifying, and substituting the first condition, we have

    c A ( y ) O P T A ( x ) ≤ 1 + α β ( c B ( y ′ ) − O P T B ( x ′ ) O P T B ( x ′ ) )

    But the term in parentheses on the right-hand side actually equals δ . Thus, the approximation ratio of A is 1 + α β δ .

    This meets the conditions for AP-reduction.

    Proof (maximization case)

    Let the approximation ratio of B be 1 1 − δ ′ . Begin with the approximation ratio of A, c A ( y ) O P T A ( x ) . We can remove absolute values around the third condition of the L-reduction definition since we know A and B are maximization problems. Substitute that condition to obtain

    c A ( y ) O P T A ( x ) ≥ O P T A ( x ) − β ( c B ( y ′ ) − O P T B ( x ′ ) ) O P T A ( x )

    Simplifying, and substituting the first condition, we have

    c A ( y ) O P T A ( x ) ≥ 1 − α β ( c B ( y ′ ) − O P T B ( x ′ ) O P T B ( x ′ ) )

    But the term in parentheses on the right-hand side actually equals δ ′ . Thus, the approximation ratio of A is 1 1 − α β δ ′ .

    If 1 1 − α β δ ′ = 1 + ϵ , then 1 1 − δ ′ = 1 + ϵ α β ( 1 + ϵ ) − ϵ , which meets the requirements for PTAS reduction but not AP-reduction.

    Other properties

    L-reductions also imply P-reduction. One may deduce that L-reductions imply PTAS reductions from this fact and the fact that P-reductions imply PTAS reductions.

    L-reductions preserve membership in APX for the minimizing case only, as a result of implying AP-reductions.

    Examples

  • Dominating set: an example with α = β = 1
  • Token reconfiguration: an example with α = 1/5, β = 2

    • References

    L-reduction Wikipedia
    (Text) CC BY-SA