L-reduction

形式陈述 ​

设 $A,B$ 是目标值非负的优化问题。L-reduction 由两个多项式时间映射 $f,g$ 与常数 $\alpha ,\beta >0$ 构成：$f$ 把 $A$ 的实例 $x$ 变为 $B$ 的实例 $f(x)$；$g$ 接收原实例 $x$ 和 $B$ 的任意可行解 $y$，返回 $A$ 的可行解。对所有 $x,y$ 要求

$${\mathrm{OPT}}_B(f(x))\le \alpha {\mathrm{OPT}}_A(x),$$$$|{\mathrm{val}}_A(g(x,y))-{\mathrm{OPT}}_A(x)|\le \beta |{\mathrm{val}}_B(y)-{\mathrm{OPT}}_B(f(x))|.$$

第一式控制最优值尺度，第二式控制解偏离最优的绝对误差如何传回。以最小化为例，若 $y$ 是 $(1+\epsilon )$ 近似，则回传解满足至多 $1+\alpha \beta \epsilon$ 的近似比公理库近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。。因此 L-reduction 保持 APX公理库APXAPX · Approximable optimization problems在 NPO 框架中存在输入规模无关常数近似比的多项式时间组合优化问题类。 成员与困难性所需的常数级误差结构，比只保持 yes/no 的Karp 归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。更强。

直觉 ​

普通归约可以把一个实例的最优值放大到巨大背景常数，使目标中很好的相对近似回到原问题后毫无意义。L-reduction 用第一常数阻止尺度失控，再用第二常数保证目标解的 gap 能线性转回原问题。

映射 $g$ 需要知道原实例和目标解，才能恢复原问题的可行结构；把它写成只依赖解字符串的函数会遗漏实例语义。

例子与边界 ​

把权值仅为 $1$ 或 $2$ 的 TSP 实例视为 metric TSP 实例，是一个直接但有结构内容的 L-reduction：完全图上的 $1/2$ 权满足三角不等式，实例、可行 tour 与目标值都不变，可取 $f,g$ 为恒等映射、$\alpha =\beta =1$。该例说明“问题版本的限制类嵌入更一般类”也必须保留可行解和数值尺度。

若某变换给目标实例额外加入一个远大于原最优值的固定成本 $M(x)$，所有目标解值都近似 $M(x)$，目标的相对误差可能极小，却对应原问题的大误差。除非 $M(x)$ 能由 $\alpha {\mathrm{OPT}}_A(x)$ 统一控制，否则第一不等式失败，这正是 L-reduction 排除的伪近似保持。

最大化与最小化可共用绝对误差形式，但把它改写成比率时方向不同。目标值为零或可取负值的问题还需调整规格。L-reduction 只是近似保持归约的一种，不能把 PTAS-reduction、AP-reduction 和 gap reduction 全部改名为 L-reduction。

推论与应用 ​

L-reduction 常用于证明 APX-hard 与 APX-complete：从已知 APX-hard 问题归约到目标，两个常数把目标的过好近似转成源问题的过好近似。归约方向、问题版本与两个数值不等式都必须逐项验证。

L-reduction 可复合，复合后的尺度和误差常数由各步常数组合得到，仍与输入规模无关。若某步常数实际依赖 $n$，链条就不再证明 APX 层面的常数保持。

参考资料

• Christos H. Papadimitriou and Mihalis Yannakakis, “Optimization, Approximation, and Complexity Classes,” Journal of Computer and System Sciences 43(3), 1991, pp. 425–440.
• Giorgio Ausiello et al., Complexity and Approximation, Springer, 1999, Ch. 8.