L-reduction

An L-reduction, short for linear reduction, is a transformation used in computational complexity theory to relate the approximability of optimization problems to one another. It plays a role for approximation algorithms similar to the role polynomial-time reductions play for decision problems: if one optimization problem can be related to another through an L-reduction, then a polynomial-time approximation scheme for the target problem can be converted into one for the source problem. Researchers use L-reductions to prove that an optimization problem is hard to approximate, or that if some easier problem admits a PTAS, then a class of related problems reachable by L-reduction from it also admits one. The technique was formalized during the 1990s alongside other approximation-preserving reductions by researchers including Viggo Kann and Pierluigi Crescenzi, who worked to classify optimization problems by how well they can be approximated in polynomial time, extending the completeness framework long used for decision problems into the approximation setting.