近似比

近似比用相对于最优值的乘法损失衡量最坏实例上算法离最优解最多差多少，因此对尺度变化稳定：所有成本同时乘十，保证不变。最小化和最大化问题的分式方向必须分别处理，常把它们统一写成算法值与最优值之比的较大者。它只描述最坏输入上的目标值，不直接反映运行时间、平均表现、某次实验误差或解的结构相似度。

有限简单无向图的顶点覆盖中，先贪心取一组两两不共享端点的边，直到再也不能添加边，得到极大匹配 $M$。输出全部匹配端点组成的集合 $S$。若某条边的两端都不在 $S$，它就还能加入 $M$，与极大性矛盾，因此 $S$ 确实覆盖所有边。

任何顶点覆盖都必须为 $M$ 中每条边选一个端点；匹配边互不相交，这些端点不能相互顶替，所以 $\mathrm{OPT}\ge |M|$。算法选了 $2|M|$ 个端点，故 $|S|=2|M|\le 2\mathrm{OPT}$。单独一条边就达到比值 $2$：算法选两端，最优只选一端。这里需要的是容易贪心得到的“极大”匹配，不是规模最大的“最大”匹配。对最大化问题，“得到最优值的 $90\mathrm{\%}$”也常称 $0.9$-approximation；本库采用比值至少为 $1$ 的对称记法时对应 $1/0.9$。必须在论文中明确约定，避免方向混淆。

非负目标可按前述不除法的约定处理零最优值；例如无边图返回空顶点覆盖，值为零。负目标仍需另定误差尺度或限制实例，不能直接套用正值分式。经验数据上“通常接近最优”也不能推出近似比，后者要求对每个允许输入成立并通常假设输出始终可行。

学习理论中的 “approximately correct” 通常使用加性风险误差。不可知 PAC 学习理路不可知 PAC 可学习性Agnostic PAC learnability不假定类内零风险真规则，而要求高概率接近比较类中的最佳风险。要求 $R_D(\hat{h})\le \underset{h\in H}{inf}{R}_D(h)+\epsilon$，而 近似 ERM理路近似 ERM 与优化误差approximate ERM · optimization error刻画训练目标未被精确最小化时，经验次优量如何进入总体超额风险。允许经验目标距最优值至多一个加性容差；当最优风险为零时，乘法近似甚至无法表达这种保证。因此 PAC 的 $\epsilon$ 不是近似比，训练目标的优化容差也必须经过风险分解后才进入总体误差。

该指标建立在优化问题理路优化问题Optimization problem在可行解集合上最小化或最大化目标函数的计算问题。的可行解与最优值上。APX理路APXAPX · Constant-factor approximable optimization problems在 NPO 框架中存在输入规模无关常数近似比的多项式时间组合优化问题类。收集具有常数近似的问题，PTAS理路多项式时间近似方案Polynomial-time approximation scheme · PTAS对每个固定 ε>0 都在多项式时间内给出 1±ε 近似的算法族。对每个固定精度给出算法；L-reduction理路L-reductionL-reduction · Linear reduction以两个常数控制目标最优值与误差回传的优化归约，保持PTAS并明确常数近似传递的方向条件。控制最优值尺度与解误差，gap reduction理路Gap 问题与 gap reductionGap problem · Gap reduction · Gap-preserving reduction以带承诺的最优值阈值间隙和保持两端阈值的归约，把局部检验可靠性转化为不可近似性。则保持两个 promise 阈值。它们使用同一比率语言，却承担不同类定义与困难性证明，不能并入近似比定义。

随机算法还要说明近似保证是对期望目标值成立，还是以至少 $1-\delta$ 的概率成立；前者不能在没有尾界时改写成后者。随机舍入理路随机舍入randomized rounding从连续松弛解生成随机离散解，以覆盖补选证明每次可行性与期望成本，并区分独立坐标与共享超平面的舍入。展示了这一区别，整数性间隙理路整数性间隙Integrality gap衡量整数最优值与其松弛最优值在最坏实例上的比值。则比较松弛最优值与整数最优值。若算法同时放松容量和目标两个指标，应明确写成 bicriteria 保证，而不是塞进单个 $\rho$。