- PTAS reduction
In
computational complexity theory , a PTAS reduction is a reduction that is often used to perform reductions between solutions tooptimization problem s. It preserves the property that a problem has apolynomial time approximation scheme (PTAS) and is used to define completeness for certain classes ofoptimization problem s such asAPX . Notationally, if there is a PTAS reduction from a problem A to a problem B, we write ext{A} leq_{ ext{PTAS ext{B}.With ordinary
polynomial-time many-one reduction s, 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 + 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.From this definition it is straightforward to show that:
* ext{A} leq_{ ext{PTAS ext{B} and ext{B} in ext{PTAS} implies ext{A} in ext{PTAS}
* ext{A} leq_{ ext{PTAS ext{B} and ext{A} otin ext{PTAS} implies ext{B} otin ext{PTAS}
* ext{A} leq_{ ext{PTAS ext{B} and ext{B} in ext{APX} implies ext{A} in ext{APX}References
* Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. ISBN 3540210458. Chapter 8, pp.110–111. [http://books.google.com/books?vid=ISBN3540210458 Google Books preview]
Wikimedia Foundation. 2010.