线性规划松弛与舍入

证明链 ​

把整数问题放宽为线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。多面体 (P) 后，

$$LP\le OP{T}_{int}.$$

设计舍入使整数输出可行且 $cost\le \alpha LP$，便有 $cost\le \alpha OPT$。可行性与目标界是两份证明；随机舍入还须说明期望、高概率与约束修复。

Vertex cover LP 令每边 $x_u+x_v\ge 1$、$0\le x_v\le 1$，选所有 $x_v\ge 1/2$。每条边至少一端被选，成本

$$\sum _{v:x_v\ge 1/2}{w}_v\le 2\sum _v{w}_v{x}_v,$$

得到 2-approximation。

边界 ​

逐坐标四舍五入可破坏全局约束，例如 set cover 中每集合变量都小于 $1/2$ 却共同覆盖。最大化时松弛给上界，比率方向相反。LP 可积不表示容易找到有用舍入；相关舍入常用于保存全局结构。

建模质量先于舍入：同一整数问题可有多个 LP。若松弛漏掉关键有效不等式，分数解过于乐观，任何仅按 LP 值证明的比率都受 integrality gap 限制。

证明必须分别建立整数可行性和目标界。只计算舍入后的期望成本，却没有处理违反约束的结果，尚未得到近似算法。

从整数模型到分数解 ​

Vertex Cover 为每点设 $x_v\in \{0,1\}$，每边约束 $x_u+x_v\ge 1$。放宽到 $[0,1]$ 后，三角形可取每点 $1/2$，LP 值 $3/2$，整数最优需选两点。按阈值 $1/2$ 舍入会选三个点，成本 3，仍不超过 2 倍 LP。

可行性证明逐边看：$x_u+x_v\ge 1$ 意味至少一个端点不小于 $1/2$；成本证明对每个被选点用 $1\le 2x_v$。两条证明缺一不可，且加权情形同样逐点乘 $w_v$。

随机舍入与修复 ​

Set cover 可按 $x_j$ 的放大概率独立选集合，期望成本易由线性期望控制，但某元素可能未覆盖；用并集界选择放大因子，再补选遗漏元素，或使用依赖舍入。直接四舍五入每个 $x_j<1/2$ 为零会让全部约束失败。

随机成本的期望界不等于高概率界；需要 Markov/Chernoff、重复取最好可行解或条件期望去随机化，并把求 LP 的多项式成本计入。

松弛选择边界 ​

最小化 LP 值是整数 OPT 下界，最大化则是上界。加强 LP 添加有效不等式可能改善 integrality gap，却增加求解/分离成本。SDP rounding 使用向量几何，不是线性舍入的同义替换。

参考资料

• Vijay Vazirani, Approximation Algorithms, 2001.
• Williamson, Shmoys, The Design of Approximation Algorithms, 2011.