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 .

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:

Properties

From the definition it is straightforward to show that:

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

  1. Crescenzi, Pierluigi (1997). "A Short Guide To Approximation Preserving Reductions". Proceedings of the 12th Annual IEEE Conference on Computational Complexity. Washington, D.C.: IEEE Computer Society: 262–.


This article is issued from Wikipedia - version of the 11/5/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.