title: L-reduction
text: 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.
  
  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
  ,
   there exists a positive constant β such that for every solution y'  to f(x)
  .
  
  Properties
  
  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 an 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 .
  Begin with the approximation ratio of A, .  
  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
   
  Simplifying, and substituting the first condition, we have
   
  But the term in parentheses on the right-hand side actually equals .  Thus, the approximation ratio of A is .
  
  This meets the conditions for AP-reduction.
  
  Proof (maximization case) 
  
  Let the approximation ratio of B be .
  Begin with the approximation ratio of A, .  
  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
   
  Simplifying, and substituting the first condition, we have
   
  But the term in parentheses on the right-hand side actually equals .  Thus, the approximation ratio of A is .
  
  If , then , 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
  
  See also
   MAXSNP
   Approximation-preserving reduction
   PTAS reduction
  
  References
  
   G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation. Combinatorial optimization problems and their approximability properties. 1999, Springer. 
  
  Reduction (complexity)
  Approximation algorithms