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.

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

Properties

From the definition it is straightforward to show that:

  • and
  • and

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.

gollark: Environments work weirdly. *Probably*, I think.
gollark: Not necessarily.
gollark: Those are built on `term.write` ultimately, but so is everything there but `term.write` and `term.blit` sooo...
gollark: `textutils` things?
gollark: There're mods to integrate it with AE2 and RS, aren't there?

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–.
  • Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. ISBN 3-540-21045-8. Chapter 8, pp. 110111. Google Books preview
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.