近似比

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

一般图顶点覆盖中，取任一极大匹配的全部端点得到大小至多最优值两倍的覆盖，因此是 2-近似。对最大化问题，“得到最优值的 $90\mathrm{\%}$”也常称 $0.9$-approximation；本库采用比值至少为 $1$ 的对称记法时对应 $1/0.9$。必须在论文中明确约定，避免方向混淆。

当最优值可能为 $0$ 或目标可取负值时，乘法比可能无定义或失去意义，需要改用加性误差、归一化目标或先限制实例。经验数据上“通常接近最优”也不能推出近似比，后者要求对每个允许输入成立并通常假设输出始终可行。

学习理论中的 “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 · Approximable optimization problems在 NPO 框架中存在输入规模无关常数近似比的多项式时间组合优化问题类。收集具有常数近似的问题，PTAS公理库多项式时间近似方案Polynomial-time approximation scheme · PTAS对每个固定 ε>0 都在多项式时间内给出 1±ε 近似的算法族。对每个固定精度给出算法；L-reduction公理库L-reductionL-reduction · Linear reduction以两个常数同时控制目标最优值尺度和解误差回传，从而保持常数近似性的优化归约。控制最优值尺度与解误差，gap reduction公理库Gap 问题与 gap reductionGap problem · Gap reduction · Gap-preserving reduction以带承诺的最优值阈值间隙和保持两端阈值的归约，把局部检验可靠性转化为不可近似性。则保持两个 promise 阈值。它们使用同一比率语言，却承担不同类定义与困难性证明，不能并入近似比定义。

随机算法还要说明近似保证是对期望目标值成立，还是以至少 $1-\delta$ 的概率成立；前者不能在没有尾界时改写成后者。随机舍入公理库随机舍入randomized rounding把分数解解释为选择概率，以期望、浓缩和修补把凸松弛转成离散近似解。展示了这一区别，整数性间隙公理库整数性间隙Integrality gap衡量整数最优值与其松弛最优值在最坏实例上的比值。则比较松弛最优值与整数最优值。若算法同时放松容量和目标两个指标，应明确写成 bicriteria 保证，而不是塞进单个 $\rho$。