L-reductions between optimization problems

Let $\mathrm{\Pi }$ and $\mathrm{\Gamma }$ be finite-instance optimization problems in the model of Optimization problems and approximation ratios, with objective directions and nonnegative rational values as specified there; write ${\mathrm{OPT}}_{\mathrm{\Pi }}(x)$ and ${\mathrm{OPT}}_{\mathrm{\Gamma }}(z)$ for their attained optima and ${\mathrm{val}}_{\mathrm{\Pi }}$, ${\mathrm{val}}_{\mathrm{\Gamma }}$ for their objective values. An L-reduction from $\mathrm{\Pi }$ to $\mathrm{\Gamma }$ consists of:

• a total instance map $f$, computable in deterministic polynomial time, that carries every instance $x$ of $\mathrm{\Pi }$ to an instance $f(x)$ of $\mathrm{\Gamma }$;
• a feasible-solution map $g$, computable in deterministic polynomial time, that on every instance $x$ of $\mathrm{\Pi }$ and every feasible solution $y$ of the $\mathrm{\Gamma }$-instance $f(x)$ produces a feasible solution $g(x,y)$ of the $\mathrm{\Pi }$-instance $x$;
• constants $a>0$ and $b>0$, independent of the instance, such that for every instance $x$ of $\mathrm{\Pi }$ and every feasible solution $y$ of $f(x)$,

${\mathrm{OPT}}_{\mathrm{\Gamma }}(f(x))\le a{\mathrm{OPT}}_{\mathrm{\Pi }}(x),\mid {\mathrm{OPT}}_{\mathrm{\Pi }}(x)-{\mathrm{val}}_{\mathrm{\Pi }}(g(x,y))\mid \le b\mid {\mathrm{OPT}}_{\mathrm{\Gamma }}(f(x))-{\mathrm{val}}_{\mathrm{\Gamma }}(y)\mid \mathrm{.}$

The first inequality relates the two optima and the second is the error transfer inequality: it compares the loss of the decoded solution to the loss of the given one. Both maps are required to be total on their stated domains and to run in time polynomial in the encoding lengths involved, and both objectives are nonnegative rationals, so the absolute values are ordinary finite differences of nonnegative numbers. The definition covers minimization and maximization problems without change; the first inequality is an ordinary comparison of nonnegative rationals and the second is stated with absolute values rather than a quotient, so instances with optimum $0$ are included. The APX-hardness and APX-completeness notions attached to this reduction are defined separately under the selected convention of APX-hardness and APX-completeness under L-reductions, and the transfer and composition properties are proved in L-reductions compose and transfer PTAS and APX-hardness. An L-reduction alone is not a promise problem or a gap-preserving reduction in the sense of Gap promise problems and gap-preserving reductions: it carries feasible solutions backwards through $g$, which a gap map need not do.