- Source: PTAS reduction
In computational complexity theory, a PTAS reduction is an approximation-preserving reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme (PTAS) and is used to define completeness for certain classes of optimization problems such as APX. Notationally, if there is a PTAS reduction from a problem A to a problem B, we write
A
≤
PTAS
B
{\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}
.
With ordinary polynomial-time many-one reductions, if we can describe a reduction from a problem A to a problem B, then any polynomial-time solution for B can be composed with that reduction to obtain a polynomial-time solution for the problem A. Similarly, our goal in defining PTAS reductions is so that given a PTAS reduction from an optimization problem A to a problem B, a PTAS for B can be composed with the reduction to obtain a PTAS for the problem A.
Definition
Formally, we define a PTAS reduction from A to B using three polynomial-time computable functions, f, g, and α, with the following properties:
f maps instances of problem A to instances of problem B.
g takes an instance x of problem A, an approximate solution to the corresponding problem
f
(
x
)
{\displaystyle f(x)}
in B, and an error parameter ε and produces an approximate solution to x.
α maps error parameters for solutions to instances of problem A to error parameters for solutions to problem B.
If the solution y to
f
(
x
)
{\displaystyle f(x)}
(an instance of problem B) is at most
1
+
α
(
ϵ
)
{\displaystyle 1+\alpha (\epsilon )}
times worse than the optimal solution, then the corresponding solution
g
(
x
,
y
,
ϵ
)
{\displaystyle g(x,y,\epsilon )}
to x (an instance of problem A) is at most
1
+
ϵ
{\displaystyle 1+\epsilon }
times worse than the optimal solution.
Properties
From the definition it is straightforward to show that:
A
≤
PTAS
B
{\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}
and
B
∈
PTAS
⟹
A
∈
PTAS
{\displaystyle {\text{B}}\in {\text{PTAS}}\implies {\text{A}}\in {\text{PTAS}}}
A
≤
PTAS
B
{\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}
and
A
∉
PTAS
⟹
B
∉
PTAS
{\displaystyle {\text{A}}\not \in {\text{PTAS}}\implies {\text{B}}\not \in {\text{PTAS}}}
L-reductions imply PTAS reductions. As a result, one may show the existence of a PTAS reduction via a L-reduction instead.
PTAS reductions are used to define completeness in APX, the class of optimization problems with constant-factor approximation algorithms.
See also
Approximation-preserving reduction
L-reduction
APX
References
Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. ISBN 3-540-21045-8. Chapter 8, pp. 110–111. Google Books preview
Kata Kunci Pencarian:
- PTAS reduction
- PTAS
- Approximation-preserving reduction
- Polynomial-time approximation scheme
- L-reduction
- APX
- SNP (complexity)
- Preferential trading area
- Set packing
- Gap reduction
