线性规划松弛与舍入

LP 松弛先把难处理的离散可行域扩成可优化的分数多面体，最优值因此成为整数最优的单向界。舍入必须同时完成两件事：把分数点送回组合可行域，并控制目标值相对松弛界的损失；只完成其中一项还不是近似证明。

边界 ​

逐坐标四舍五入可破坏全局约束，例如 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 使用向量几何，不是线性舍入的同义替换。