Projective cone

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.

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 a positive constant α such that

$\mathrm{O}\mathrm{P}{\mathrm{T}}_{\mathrm{B}}(f(x))\le \alpha \mathrm{O}\mathrm{P}{\mathrm{T}}_{\mathrm{A}}(x)$,

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

$|\mathrm{O}\mathrm{P}{\mathrm{T}}_{\mathrm{A}}(x)-c_A(g(y))|\le \beta |\mathrm{O}\mathrm{P}{\mathrm{T}}_{\mathrm{B}}(f(x))-c_B(y)|$.

Properties

Let a (1±ε)-approximation algorithm f for a problem A be such that $c_{\mathrm{A}}(f(x))$ is at most $\epsilon \cdot \mathrm{O}\mathrm{P}{\mathrm{T}}_{\mathrm{A}}(x)$ away from $\mathrm{O}\mathrm{P}{\mathrm{T}}_{\mathrm{A}}(x)$, 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 $\delta =\alpha \beta \epsilon$. This implies that if B has a polynomial-time approximation scheme then so does A.

See also

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

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

• 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