L-reduction Information & L-reduction Links at HealthHaven.com

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.

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.

[edit] Definition

Let A and B be optimization problems and c_A and c_B 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 such positive constant α that

$\mathrm{OPT_B}(f(x)) \le \alpha \mathrm{OPT_A}(x)$ ,

there exists such positive constant β that for every solution y to f(x)

$|\mathrm{OPT_A}(x)-c_A(g(y))| \le \beta |\mathrm{OPT_B}(f(x))-c_B(y)|$ .

[edit] Properties

Let an ε-approximation algorithm f for a problem A be such that $\mathrm{OPT_A(x)}^{-1}|\mathrm{OPT_A}(x) - c_\mathrm{A}(f(x))| \le \varepsilon$ for every instance x (using the convention that 0 / 0 = 0).

It can be shown that if (f,g,α,β) is an L-reduction of problem A to B and there exists an ε-approximation algorithm for B then there also exists a polynomial δ-approximation algorithm for A where $\delta = \alpha \beta \varepsilon$ .^[1]^[2] This also implies that if B has a polynomial-time approximation scheme then so does A.

[edit] See also

MAXSNP
PTAS reduction
Dominating set#L-reductions: an example with α = β = 1

[edit] References

^ 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:http://doi.acm.org/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.

[Kann92-0] Kann, Viggo (1992). On the Approximability of NP-complete Optimization Problems. Royal Institute of Technology, Sweden. ISBN 91-7170-082-X.

[Papadimitriou88-1] 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:http://doi.acm.org/10.1145/62212.62233.

[1]

[2]

Contents

[edit] Definition

[edit] Properties

[edit] See also

[edit] References