APX

形式陈述 ​

APX 定义在 NPO 优化问题上。一个 NPO 问题先给出多项式时间可识别的实例集合；对每个实例 $I$，给出非空可行解集 $F(I)$，其中每个解的编码长度由 $|I|$ 的同一个多项式界定，且关系“$y\in F(I)$”可在多项式时间验证。目标函数 $m(I,y)$ 也须能在多项式时间计算，并明确求最小还是最大。这里要求可行性与目标值容易核验，不要求能在多项式时间找到最优解；后者正是近似分类要研究的困难。

对每个实例 $I$，令 $A(I)=m(I,y_A)$ 是多项式时间算法输出的某个可行解值，$\mathrm{OPT}(I)>0$ 是 $F(I)$ 上的最优值。本页统一采用至少为 $1$ 的近似比公理库近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。：最小化问题要求

$$\frac{A(I)}{\mathrm{OPT}(I)}\le \rho ,$$

最大化问题要求

$$\frac{\mathrm{OPT}(I)}{A(I)}\le \rho .$$

若某个与输入规模无关的常数 $\rho \ge 1$ 和一个多项式时间公理库复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。算法对所有合法实例满足相应不等式，则该问题属于 APX。常数可以依赖问题，但不能依赖实例。能对每个固定 $\epsilon >0$ 达到 $1+\epsilon$ 保证的问题属于 PTAS，故 $PTAS\subseteq APX$；APX-hard 与 APX-complete 则必须相对于明确的近似保持归约定义。

直觉 ​

APX 表示可以用统一常数控制最坏情况下的目标损失。它比“有某个启发式通常不错”强，因为保证覆盖每个允许输入；又比 PTAS 弱，因为常数不必能任意逼近 $1$。类的中心是可证明的近似质量与多项式时间同时成立，而不是算法在一批样例上的平均表现。

优化问题公理库优化问题Optimization problem在可行解集合上最小化或最大化目标函数的计算问题。的版本必须固定。是否带权、是否满足三角不等式、目标是最大化还是最小化，都可能改变成员资格和最佳比率；只写问题简称会把不同问题误装进同一个类。

例子与边界 ​

一般图最小顶点覆盖有一个 2-近似：取任意极大匹配，把每条匹配边的两个端点全部加入覆盖。任一覆盖至少要为每条互不共享端点的匹配边选一个端点，因此算法使用的 $2|M|$ 个顶点至多是最优值的两倍。这是 APX 成员证明，因为可行性、时间界和常数比都有独立证据。

Metric TSP 具有常数近似算法，但若移除三角不等式，同一“旅行商问题”版本就不能沿用捷径化分析。这个差别不是数字换成另一常数，而是关键结构假设消失：跳过已访问顶点时，直接边可能比绕行更贵，证明的核心不等式不再成立。

有一个 1000-近似仍足以证明属于 APX；APX 不声称该常数优良或最优。反过来，近似比为 $O(\log n)$ 的算法不能据此归入 APX，因为保证随规模增长。若 $\mathrm{OPT}$ 可为零或目标取负值，乘法比可能无定义，必须先限制问题或改用合适误差尺度。

推论与应用 ​

APX 为常数近似、PTAS 和不可近似性提供共同坐标。近似保持归约可以传递 APX-hardness；若一个 APX-hard 问题拥有 PTAS，通常会推出相应复杂度坍塌，但结论取决于归约类型和标准假设，不能只凭“NP-hard”三个字得出。

设计 APX 算法时，局部搜索、原始—对偶、舍入和匹配结构常给出常数证书。分类时则应把具体问题版本、可行解编码、目标方向、比率 convention 与运行模型全部写明，才能比较来自不同来源的界。

参考资料

• Giorgio Ausiello et al., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 1999, Chs. 1–2.
• Christos H. Papadimitriou and Mihalis Yannakakis, “Optimization, Approximation, and Complexity Classes,” Journal of Computer and System Sciences 43(3), 1991, pp. 425–440.