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.
Definitionedit
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:
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)
.
Propertiesedit
Implication of PTAS reductionedit
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.[1][2] 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.[3]
Proof (minimization case)edit
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)edit
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 propertiesedit
L-reductions also imply P-reduction.[3] 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.
^Kann, Viggo (1992). On the Approximability of NP-complete \mathrm{OPT}imization Problems. Royal Institute of Technology, Sweden. ISBN 978-91-7170-082-7.
^Christos H. Papadimitriou; Mihalis Yannakakis (1988). "\mathrm{OPT}imization, Approximation, and Complexity Classes". STOC '88: Proceedings of the twentieth annual ACM Symposium on Theory of Computing. doi:10.1145/62212.62233.
^ abCrescenzi, Pierluigi (1997). "A short guide to approximation preserving reductions". Proceedings of Computational Complexity. Twelfth Annual IEEE Conference. Washington, D.C.: IEEE Computer Society. pp. 262–. doi:10.1109/CCC.1997.612321. ISBN 9780818679070. S2CID 18911241.
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. ISBN 3-540-65431-3