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 $\text \leq_ \text$.

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

Properties

From the definition it is straightforward to show that:
* $\text \leq_ \text$ and $\text \in \text \implies \text \in \text$
* $\text \leq_ \text$ and $\text \not\in \text \implies \text \not\in \text$

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

Reduction (complexity)
Approximation algorithms