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 [math]\displaystyle{ \text{A} \leq_{\text{PTAS}} \text{B} }[/math]. 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.[citation needed]
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 [math]\displaystyle{ f(x) }[/math] 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 [math]\displaystyle{ f(x) }[/math] (an instance of problem B) is at most [math]\displaystyle{ 1 + \alpha(\epsilon) }[/math] times worse than the optimal solution, then the corresponding solution [math]\displaystyle{ g(x,y,\epsilon) }[/math] to x (an instance of problem A) is at most [math]\displaystyle{ 1 + \epsilon }[/math] times worse than the optimal solution.
Properties
From the definition it is straightforward to show that:
- [math]\displaystyle{ \text{A} \leq_{\text{PTAS}} \text{B} }[/math] and [math]\displaystyle{ \text{B} \in \text{PTAS} \implies \text{A} \in \text{PTAS} }[/math]
- [math]\displaystyle{ \text{A} \leq_{\text{PTAS}} \text{B} }[/math] and [math]\displaystyle{ \text{A} \not\in \text{PTAS} \implies \text{B} \not\in \text{PTAS} }[/math]
L-reductions imply PTAS reductions. As a result, one may show the existence of a PTAS reduction via a L-reduction instead.[1]
PTAS reductions are used to define completeness in APX, the class of optimization problems with constant-factor approximation algorithms.
See also
References
- ↑ Crescenzi, Pierluigi (1997). "A short guide to approximation preserving reductions". Proceedings of Computational Complexity. Twelfth Annual IEEE Conference. Washington, D.C.: IEEE Computer Society. pp. 262–. doi:10.1109/CCC.1997.612321. ISBN 0-8186-7907-7. http://dl.acm.org/citation.cfm?id=792302.
- Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. ISBN 3-540-21045-8. Chapter 8, pp. 110–111. Google Books preview
 |  |
