In computer science, in particular in the study of approximation algorithms, an L-reduction ("linear reduction") is a transformation of optimization problems which linearly preserves 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.
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)
Let a (1±ε)-approximation algorithm f for a problem A be such that is at most away from , for every instance x. (In this notation, + implicitly means a minimization problem, and means a maximization problem.)
The main point of an L-reduction is the following: given a (f,g,α,β) L-reduction from problem A to problem B, and a (1±ε)-approximation algorithm for B, we obtain a polynomial-time (1±δ)-approximation algorithm for A where . This implies that if B has a polynomial-time approximation scheme then so does A.
- Kann, Viggo (1992). On the Approximability of NP-complete Optimization Problems. Royal Institute of Technology, Sweden. ISBN 91-7170-082-X.
- Christos H. Papadimitriou; Mihalis Yannakakis (1988). "Optimization, Approximation, and Complexity Classes". STOC '88: Proceedings of the twentieth annual ACM Symposium on Theory of Computing. doi:10.1145/62212.62233.
- Pierluigi Crescenzi: A Short Guide to Approximation Preserving Reductions. In: Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, June 24-27, 1997, Ulm, Germany. Pages 262-273. IEEE Computer Society Press, 1997. ISBN 0-8186-7907-7
- 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
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|