PTAS reduction

${\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}$

With ordinary

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

Properties

From the definition it is straightforward to show that:

• ${\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}$ and ${\displaystyle {\text{B}}\in {\text{PTAS}}\implies {\text{A}}\in {\text{PTAS}}}$
• ${\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}$ and ${\displaystyle {\text{A}}\not \in {\text{PTAS}}\implies {\text{B}}\not \in {\text{PTAS}}}$