PTAS reduction

From Wikipedia, the free encyclopedia

In computational complexity theory, a PTAS reduction is a 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 $\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.

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)$ 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)$ (an instance of problem B) is at most $1 + α(ε)$ times worse than the optimal solution, then the corresponding solution $g (x, y,ε)$ to x (an instance of problem A) is at most $1 + ε$ times worse than the optimal solution.

From this definition it is straightforward to show that:

$\text{A} \leq_{\text{PTAS}} \text{B}$ and $\text{B} \in \text{PTAS} \implies \text{A} \in \text{PTAS}$
$\text{A} \leq_{\text{PTAS}} \text{B}$ and $\text{A} \not\in \text{PTAS} \implies \text{B} \not\in \text{PTAS}$
$\text{A} \leq_{\text{PTAS}} \text{B}$ and $\text{B} \in \text{APX} \implies \text{A} \in \text{APX}$