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

Before giving the definition, we recall some concepts of optimization problems, illustrated with the travelling salesman problem (TSP). First an instance is the input of the problem, i.e. the information we need to compute a solution. An instance for TSP is a finite set to be the cost of an optimal solution, i.e. the length of a shortest tour. 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:

• 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

• ,

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

• .

Example

Here is a L-reduction from MAX 3-SAT to MAX 2-SAT. is the formula:

is a new variable.

). We can prove that:

• ;

• .

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)

. 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

Simplifying, and substituting the first condition, we have

.

This meets the conditions for AP-reduction.

Proof (maximization case)

. 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

Simplifying, and substituting the first condition, we have

.

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