L-reductions compose and transfer PTAS and APX-hardness

Fix an instance $x$ of $\mathrm{\Pi }$, write $x^{\mathrm{\prime }}=f(x)$, and let $y$ be a feasible solution of $x^{\mathrm{\prime }}$. By [F1] the maps $f$ and $g$ are polynomial time, the defining inequalities are ${\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})\le a{\mathrm{OPT}}_{\mathrm{\Pi }}(x)$ and $\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Pi }}(x)-{\mathrm{val}}_{\mathrm{\Pi }}(g(x,y))\mathrm{\mid }\le b\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})-{\mathrm{val}}_{\mathrm{\Gamma }}(y)\mathrm{\mid }$, and by [F2] all optima and values are attained nonnegative rationals, so each of these expressions is a finite nonnegative difference and all values are computed in polynomial time.

Composition: suppose in addition that $(f^{\mathrm{\prime }},g^{\mathrm{\prime }},a^{\mathrm{\prime }},b^{\mathrm{\prime }})$ is an L-reduction from $\mathrm{\Gamma }$ to a third problem $\mathrm{\Delta }$. Define $F(x):=f^{\mathrm{\prime }}(f(x))$ and $G(x,z):=g(x,g^{\mathrm{\prime }}(f(x),z))$ for every instance $x$ of $\mathrm{\Pi }$ and feasible $\mathrm{\Delta }$-solution $z$ of $F(x)$; these are compositions of polynomial-time maps and produce feasible solutions. The two defining inequalities give ${\mathrm{OPT}}_{\mathrm{\Delta }}(F(x))\le a^{\mathrm{\prime }}{\mathrm{OPT}}_{\mathrm{\Gamma }}(f(x))\le a^{\mathrm{\prime }}a{\mathrm{OPT}}_{\mathrm{\Pi }}(x)$ and $\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Pi }}(x)-{\mathrm{val}}_{\mathrm{\Pi }}(G(x,z))\mathrm{\mid }\le b\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Gamma }}(f(x))-{\mathrm{val}}_{\mathrm{\Gamma }}(g^{\mathrm{\prime }}(f(x),z))\mathrm{\mid }\le b{b}^{\mathrm{\prime }}\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Delta }}(F(x))-{\mathrm{val}}_{\mathrm{\Delta }}(z)\mathrm{\mid }$, so $(F,G,a^{\mathrm{\prime }}a,b{b}^{\mathrm{\prime }})$ is an L-reduction from $\mathrm{\Pi }$ to $\mathrm{\Delta }$ by [F1].

Relative-error transfer for positive target optimum: suppose ${\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})>0$ and the feasible solution $y$ satisfies ${\mathrm{val}}_{\mathrm{\Gamma }}(y)\le (1+ϵ){\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})$ in the minimization direction or ${\mathrm{val}}_{\mathrm{\Gamma }}(y)\ge (1-ϵ){\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})$ in the maximization direction, that is, its relative error in $\mathrm{\Gamma }$'s direction is at most $ϵ$ in the value sense of [F3]. Since ${\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})$ is an attained minimum in the first case, ${\mathrm{val}}_{\mathrm{\Gamma }}(y)\ge {\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})$ there, and since it is an attained maximum in the second case, ${\mathrm{val}}_{\mathrm{\Gamma }}(y)\le {\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})$ there; in both cases $\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})-{\mathrm{val}}_{\mathrm{\Gamma }}(y)\mathrm{\mid }\le ϵ{\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})$.

APX-hardness transfer: assume $\mathrm{\Pi }$ is APX-hard under the selected convention [F4] and let $\mathrm{\Lambda }$ be any problem in APX. By APX-hardness of $\mathrm{\Pi }$ there is an L-reduction from $\mathrm{\Lambda }$ to $\mathrm{\Pi }$ with constants $(a^{\mathrm{\prime }},b^{\mathrm{\prime }})$; composing it with the reduction $(f,g,a,b)$ of step 1.1 by the construction of step 2.1 gives an L-reduction from $\mathrm{\Lambda }$ to $\mathrm{\Gamma }$ with constants $(a^{\mathrm{\prime }}a,b{b}^{\mathrm{\prime }})$. Since $\mathrm{\Lambda }\in \mathrm{A}\mathrm{P}\mathrm{X}$ was arbitrary, every problem in APX L-reduces to $\mathrm{\Gamma }$, so $\mathrm{\Gamma }$ is APX-hard by [F4].

Error bound: applying the second L-reduction inequality of step 1.1 to the solution $y$ of step 2.2 and then the optimum bound of [F1], $\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Pi }}(x)-{\mathrm{val}}_{\mathrm{\Pi }}(g(x,y))\mathrm{\mid }\le b\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})-{\mathrm{val}}_{\mathrm{\Gamma }}(y)\mathrm{\mid }\le bϵ{\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})\le abϵ{\mathrm{OPT}}_{\mathrm{\Pi }}(x)$. If ${\mathrm{OPT}}_{\mathrm{\Pi }}(x)>0$, dividing by it bounds the relative error in $\mathrm{\Pi }$'s direction by $abϵ$; if ${\mathrm{OPT}}_{\mathrm{\Pi }}(x)=0$, the displayed chain gives $\mathrm{\mid }{\mathrm{val}}_{\mathrm{\Pi }}(g(x,y))\mathrm{\mid }\le 0$, so the decoded solution is optimal.

Zero target optimum: suppose ${\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})=0$. If $\mathrm{\Gamma }$ is a minimization problem, the ratio guarantee gives ${\mathrm{val}}_{\mathrm{\Gamma }}(y)\le (1+ϵ)\cdot 0=0$ and [F2] gives ${\mathrm{val}}_{\mathrm{\Gamma }}(y)\ge 0$, so ${\mathrm{val}}_{\mathrm{\Gamma }}(y)=0$; if $\mathrm{\Gamma }$ is a maximization problem, ${\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})=0$ is the largest feasible value and all values are nonnegative, so again ${\mathrm{val}}_{\mathrm{\Gamma }}(y)=0$. Then the L-reduction error inequality gives $\mathrm{\mid }{\mathrm{OPT}}_{\mathrm{\Pi }}(x)-{\mathrm{val}}_{\mathrm{\Pi }}(g(x,y))\mathrm{\mid }\le b\cdot 0=0$, so the decoded $\mathrm{\Pi }$-solution is optimal. The same conclusion holds when ${\mathrm{OPT}}_{\mathrm{\Pi }}(x)=0$, because then ${\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})\le a\cdot 0=0$ and nonnegativity give ${\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})=0$, reducing to the case just treated.

PTAS transfer: let $(A_{ϵ}{)}_{0<ϵ<1}$ be a PTAS for $\mathrm{\Gamma }$ by [F3] and let $\eta \in (0,1)$ be a rational tolerance for $\mathrm{\Pi }$. Choose a rational $ϵ$ with $0<ϵ<\min (1\mathrm{/}2,\eta \mathrm{/}(2ab))$, which is possible because $ab>0$ and $\eta >0$, so that $abϵ<\eta$ and $abϵ<1\mathrm{/}2$. Run $A_{ϵ}$ on $x^{\mathrm{\prime }}=f(x)$ to obtain a feasible $y$, then decode $g(x,y)$. If ${\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})>0$, step 3.2 bounds the relative error of the decoded solution by $abϵ<\eta$; if ${\mathrm{OPT}}_{\mathrm{\Gamma }}(x^{\mathrm{\prime }})=0$, step 4.1 shows the decoded solution is optimal, a relative error of $0<\eta$. The running time is polynomial in $\mathrm{\mid }x\mathrm{\mid }$, being a composition of the polynomial map $f$, the fixed-$ϵ$ polynomial algorithm $A_{ϵ}$, and the polynomial map $g$; hence $\mathrm{\Gamma }\in \mathrm{P}\mathrm{T}\mathrm{A}\mathrm{S}$ implies $\mathrm{\Pi }\in \mathrm{P}\mathrm{T}\mathrm{A}\mathrm{S}$.

Consequently an L-reduction transfers relative-error guarantees and PTAS membership, L-reductions compose with constants $(a{a}^{\mathrm{\prime }},b{b}^{\mathrm{\prime }})$, and by step 3.1 the APX-hardness of a problem transfers to any L-reduction target under the selected convention. These conclusions rest on the value inequalities and polynomial maps of [F1]; a PCP gap bound or a no-PTAS theorem alone proves no APX-hardness statement and is not used here.