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 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(f(x)) \le \alpha \mathrm(x)$,
* there exists a positive constant β such that for every solution ''y' '' to ''f''(''x'')
:$, \mathrm(x)-c_A(g(y')), \le \beta , \mathrm(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. 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.

Proof (minimization case)

Let the approximation ratio of B be $1 + \delta$.
Begin with the approximation ratio of A, $\frac$.
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 \le \frac$
Simplifying, and substituting the first condition, we have
: $\frac \le 1 + \alpha \beta \left( \frac \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$.
Begin with the approximation ratio of A, $\frac$.
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 \ge \frac$
Simplifying, and substituting the first condition, we have
: $\frac \ge 1 - \alpha \beta \left( \frac \right)$
But the term in parentheses on the right-hand side actually equals $\delta'$. Thus, the approximation ratio of A is $\frac$.

If $\frac = 1+\epsilon$, then $\frac = 1 + \frac$, which meets the requirements for PTAS reduction but not AP-reduction.

Other properties

L-reductions also imply P-reduction. 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

See also

* MAXSNP
* Approximation-preserving reduction
* PTAS reduction

References

* 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.

{{comp-sci-theory-stub

Reduction (complexity)
Approximation algorithms