- Source: 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:
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
O
P
T
B
(
f
(
x
)
)
≤
α
O
P
T
A
(
x
)
{\displaystyle \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)
|
O
P
T
A
(
x
)
−
c
A
(
g
(
y
′
)
)
|
≤
β
|
O
P
T
B
(
f
(
x
)
)
−
c
B
(
y
′
)
|
{\displaystyle |\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. 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
+
δ
{\displaystyle 1+\delta }
.
Begin with the approximation ratio of A,
c
A
(
y
)
O
P
T
A
(
x
)
{\displaystyle {\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
c
A
(
y
)
O
P
T
A
(
x
)
≤
O
P
T
A
(
x
)
+
β
(
c
B
(
y
′
)
−
O
P
T
B
(
x
′
)
)
O
P
T
A
(
x
)
{\displaystyle {\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
c
A
(
y
)
O
P
T
A
(
x
)
≤
1
+
α
β
(
c
B
(
y
′
)
−
O
P
T
B
(
x
′
)
O
P
T
B
(
x
′
)
)
{\displaystyle {\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
δ
{\displaystyle \delta }
. Thus, the approximation ratio of A is
1
+
α
β
δ
{\displaystyle 1+\alpha \beta \delta }
.
This meets the conditions for AP-reduction.
Proof (maximization case)
Let the approximation ratio of B be
1
1
−
δ
′
{\displaystyle {\frac {1}{1-\delta '}}}
.
Begin with the approximation ratio of A,
c
A
(
y
)
O
P
T
A
(
x
)
{\displaystyle {\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
c
A
(
y
)
O
P
T
A
(
x
)
≥
O
P
T
A
(
x
)
−
β
(
c
B
(
y
′
)
−
O
P
T
B
(
x
′
)
)
O
P
T
A
(
x
)
{\displaystyle {\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
c
A
(
y
)
O
P
T
A
(
x
)
≥
1
−
α
β
(
c
B
(
y
′
)
−
O
P
T
B
(
x
′
)
O
P
T
B
(
x
′
)
)
{\displaystyle {\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
δ
′
{\displaystyle \delta '}
. Thus, the approximation ratio of A is
1
1
−
α
β
δ
′
{\displaystyle {\frac {1}{1-\alpha \beta \delta '}}}
.
If
1
1
−
α
β
δ
′
=
1
+
ϵ
{\displaystyle {\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon }
, then
1
1
−
δ
′
=
1
+
ϵ
α
β
(
1
+
ϵ
)
−
ϵ
{\displaystyle {\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. 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. ISBN 3-540-65431-3
Kata Kunci Pencarian:
- Reduction print
- Vibration Reduction
- Michael L. Gernhardt
- Syamsul Ma'arif
- Kemacetan
- Mawardy Nurdin
- Globalisasi
- Atorvastatin
- Renminbi
- MP3
- L-reduction
- Reduction
- Log-space reduction
- Many-one reduction
- Reductionism
- Redox
- Breast reduction
- Approximation-preserving reduction
- Reduction potential
- Oxymercuration reaction
