L-reduction

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

In computer science, particularly the study of approximation algorithms, an L-reduction ("linear reduction") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preserving reduction. 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 {OPT_{B}} (f(x))\leq \alpha \mathrm {OPT_{A}} (x)

,

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

|\mathrm {OPT_{A}} (x)-c_{A}(g(y'))|\leq \beta |\mathrm {OPT_{B}} (f(x))-c_{B}(y')|

.

Properties

Implication of PTAS reduction

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)

Let the approximation ratio of B be $1+\delta$ . Begin with the approximation ratio of A, ${\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}$ . 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

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq {\frac {\mathrm {OPT} _{A}(x)+\beta (c_{B}(y')-\mathrm {OPT} _{B}(x'))}{\mathrm {OPT} _{A}(x)}}

Simplifying, and substituting the first condition, we have

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq 1+\alpha \beta \left({\frac {c_{B}(y')-\mathrm {OPT} _{B}(x')}{\mathrm {OPT} _{B}(x')}}\right)

But the term in parentheses on the right-hand side actually equals $\delta$ . Thus, the approximation ratio of A is $1+\alpha \beta \delta$ .

This meets the conditions for AP-reduction.

Proof (maximization case)

Let the approximation ratio of B be ${\frac {1}{1-\delta '}}$ . Begin with the approximation ratio of A, ${\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}$ . 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

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq {\frac {\mathrm {OPT} _{A}(x)-\beta (c_{B}(y')-\mathrm {OPT} _{B}(x'))}{\mathrm {OPT} _{A}(x)}}

Simplifying, and substituting the first condition, we have

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq 1-\alpha \beta \left({\frac {c_{B}(y')-\mathrm {OPT} _{B}(x')}{\mathrm {OPT} _{B}(x')}}\right)

But the term in parentheses on the right-hand side actually equals $\delta '$ . Thus, the approximation ratio of A is ${\frac {1}{1-\alpha \beta \delta '}}$ .

If ${\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon$ , then ${\frac {1}{1-\delta '}}=1+{\frac {\epsilon }{\alpha \beta (1+\epsilon )-\epsilon }}$ , which meets the requirements for PTAS reduction but not AP-reduction.

Other properties

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.

Examples

Dominating set: an example with α = β = 1
Token reconfiguration: an example with α = 1/5, β = 2

References

^ 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.
^ ^a ^b Crescenzi, 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

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

[Kann92-1] Kann, Viggo (1992). On the Approximability of NP-complete \mathrm{OPT}imization Problems. Royal Institute of Technology, Sweden. ISBN 978-91-7170-082-7.

[Papadimitriou88-2] 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.

[crescenzi-3] Crescenzi, 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.

[1]

[2]

[3]