整数性间隙

定义方向 ​

对LP 松弛与舍入公理库线性规划松弛与舍入LP relaxation and rounding放宽整数可行域获得可计算界，再把分数解舍入为可行组合解。所选的具体松弛，最小化问题的 gap 为 [ \sup_I\frac{\operatorname{OPT}{int}(I)} {\operatorname{OPT}(I)}, ] 最大化取相反方向 (\operatorname{OPT}{relax}/\operatorname{OPT})，使比值至少 1。Instance gap 是单个实例的比值，integrality gap 通常指指定实例族上的最坏上确界。

分母为 0 时乘法比值无意义，必须排除或单独定义 additive gap。这里的“relax”是松弛问题的最优值，不能用求解器尚未收敛时的某个可行分数值代替。

上下界是两种证明任务 ​

证明 gap 至多 (\alpha)，要对每个实例把最优分数解变成成本至多 (\alpha\operatorname{OPT}_{relax}) 的整数解；这通常是一条舍入定理。证明 gap 至少 (\alpha)，只需构造实例族 (I_n)，使相应比值趋近 (\alpha)。

三角形 vertex cover 的整数最优值为 2，标准 LP 可令每个顶点取 (1/2)，值为 (3/2)，所以该实例 gap 是 (4/3)。它只是一个下界实例，并没有证明最坏 gap 为 2。

完整图 (K_n) 的最小 vertex cover 有 (n-1) 个顶点，而同一 LP 的对称分数解值为 (n/2)。比值 [ \frac{n-1}{n/2}=2-\frac2n ] 趋近 2，给出标准 LP gap 至少为 2；经典阈值舍入又给出至多 2，于是上下界吻合。

Gap 属于松弛而非问题名称 ​

Gap 是“实例族加松弛族”的性质，不是 LP 求解器的数值误差，也不是优化问题脱离公式后的固定常数。加入奇环约束、有效不等式或更高层层级会改变可行分数域，得到的是一个新松弛与新的 gap。

使用 SDP、局部搜索或输入的额外结构也可能突破旧 LP gap。这不表示算法“战胜了”针对该松弛的下界，而是它的证明信息已经不只来自旧分数最优值。

Gap 对舍入算法的限制 ​

若算法的全部保证是 [ \operatorname{cost}(A(I)) \le\alpha\operatorname{OPT}_{relax}(I), ] 那么 gap 实例迫使 (\alpha) 至少达到该 gap，否则会声称一个比整数最优值更小的整数解。这个限制针对“只以该松弛值为下界”的分析路线，不是所有可能算法。

Additive gap 衡量两最优值之差，适合某些分母很小的情形，但不能与乘法近似比互换。报告 gap 时应明确最小化/最大化方向、实例族、具体松弛以及零最优值约定。

参考资料

• Vijay Vazirani, Approximation Algorithms, 2001.
• Williamson, Shmoys, 2011.
• Alexander Schrijver, Combinatorial Optimization, 2003.