整数性间隙 | Codeboy's Blog

形式陈述

对LP 松弛与舍入所选的具体松弛，最小化问题的 gap 为

\sup_I\frac{\operatorname{OPT}_{int}(I)} {\operatorname{OPT}_{relax}(I)},

最大化取相反方向 $\operatorname{OPT}_{relax}/\operatorname{OPT}_{int}$ ，使比值至少 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 是“实例族加松弛族”的性质，不是 LP 求解器的数值误差，也不是优化问题脱离公式后的固定常数。加入奇环约束、有效不等式或更高层层级会改变可行分数域，得到的是一个新松弛与新的 gap。

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

例子与边界

若算法的全部保证是

\operatorname{cost}(A(I)) \le\alpha\operatorname{OPT}_{relax}(I),

那么 gap 实例迫使 $\alpha$ 至少达到该 gap，否则会声称一个比整数最优值更小的整数解。这个限制针对“只以该松弛值为下界”的分析路线，不是所有可能算法。

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

推论与应用

整数性间隙同时给出舍入分析的目标与障碍：上界通常来自把任意分数最优解舍入，并把所得近似比与 gap 对齐；匹配下界则由坏实例族证明该松弛无法支撑更强比率。加入有效不等式、提升到更强层级或改用半定松弛后，应把它视为新松弛并重新测量 gap。

参考资料