L-reduction

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 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:

\mathrm{OPT_B}(f(x)) \le \alpha \mathrm{OPT_A}(x),
|\mathrm{OPT_A}(x)-c_A(g(y'))| \le \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 a 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)}{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)}{OPT_A(x)} \le \frac{OPT_A(x) + \beta(c_B(y') - OPT_B(x'))}{OPT_A(x)}

Simplifying, and substituting the first condition, we have

\frac{c_A(y)}{OPT_A(x)} \le 1 + \alpha \beta \left( \frac{c_B(y')-OPT_B(x')}{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)}{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)}{OPT_A(x)} \ge \frac{OPT_A(x) - \beta(c_B(y') - OPT_B(x'))}{OPT_A(x)}

Simplifying, and substituting the first condition, we have

\frac{c_A(y)}{OPT_A(x)} \ge 1 - \alpha \beta \left( \frac{c_B(y')-OPT_B(x')}{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

See also

References

  1. Kann, Viggo (1992). On the Approximability of NP-complete Optimization Problems. Royal Institute of Technology, Sweden. ISBN 91-7170-082-X.
  2. 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.
  3. 1 2 Crescenzi, Pierluigi (1997). "A Short Guide To Approximation Preserving Reductions". Proceedings of the 12th Annual IEEE Conference on Computational Complexity (Washington, D.C.: IEEE Computer Society): 262–.
This article is issued from Wikipedia - version of the Tuesday, May 26, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.