30篇的无权点覆盖算法把一条未覆盖边的两个端点都选入答案，依靠不相交边数提供下界。加上权重后，这个规则会失效：单条边两端成本1和K，直接全选会付出K+1，最优却只需1。

加权问题仍能得到2近似，但下界必须反映权重。28篇的线性规划对偶为此提供一组可核对的不等式；先从整数约束放宽到分数解，再说明怎样产生整数覆盖。

松弛保留什么约束

输入是无向无自环图G=(V,E)，每个顶点有非负权重w_v。输出点覆盖C，使每条边至少有一个端点被选中，目标最小化Σ_{v∈C}w_v。教学实现用整数权重；下面的证明同样适用于精确的非负有理数。

整数规划为每个顶点设置变量x_v∈{0,1}，每条边uv要求x_u+x_v≥1。把整数限制放宽成x_v≥0，得到

min⁡∑vwvxv,xu+xv≥1 (uv∈E),xv≥0.\min\sum_v w_vx_v,\qquad x_u+x_v\ge1\ (uv\in E),\quad x_v\ge0.

不必额外写x_v≤1：非负权下把大于1的坐标截成1，仍然可行，且不会增加目标值。记该松弛最优值为LP，整数最优值为OPT。每个整数解也是分数可行解，因此LP≤OPT；方向不能反过来。

若已经拿到一个最优分数解x*，取C={v:x*_v≥1/2}。每条边两端之和至少1，至少一端不小于1/2，所以C覆盖所有边。每个被选中顶点满足w_v≤2w_vx*_v，从而w©≤2LP≤2OPT。

阈值必须包含等号。只有一条边且x=(1/2,1/2)时，用严格大于1/2会返回空集，连可行性都丢失。若拿到的只是任意可行分数解，仍能证明w©≤2w·x，却不能据此推出2OPT；“可行”不能代替“最优”。

给每条边分配可支付的预算

对应的对偶问题是

max⁡∑e∈Eye,∑e∋vye≤wv (v∈V),ye≥0.\max\sum_{e\in E}y_e,\qquad\sum_{e\ni v}y_e\le w_v\ (v\in V),\quad y_e\ge0.

每个顶点限制所有关联边的预算总和。任意对偶可行y都给出下界Σy_e≤OPT：任取一个整数覆盖C，每条边至少被C中的一个顶点计入，再利用顶点约束，就有Σy_e≤Σ_{v∈C}Σ_{e∋v}y_e≤w©。

这个下界只需要弱对偶；不要求实现通用LP求解器，也不需要证明当前y已经最优。原始对偶算法会同步产生一个覆盖与一个对偶可行解，使它们的成本差不超过因子2。

从未覆盖边增加预算

初始所有y_e=0，顶点剩余预算slack_v=w_v。剩余预算为0的顶点称为紧顶点，先把全部零权顶点加入C。它们不花成本，且若不提前处理，某些未覆盖边会只能增加0预算，容易使循环无法取得进展。

逐条扫描边uv。若已有端点属于C，这条边已经覆盖，不改变预算。否则取δ=min(slack_u,slack_v)，把y_uv增加δ，并把两端剩余预算各减δ。任何新变紧的端点都加入C。

δ不会超过任何一端剩余预算，其他顶点的预算约束没有变化，所以y始终可行。每次处理未覆盖边，至少一端变紧并进入C；之后C只增不减。因此扫描结束，每条边都已覆盖。

关键不变量是：加入C的顶点一直保持紧。后续算法不再给与C相接的边增加预算，不会让紧顶点的约束超出上限。因此对每个v∈C，w_v=Σ_{e∋v}y_e，零权顶点也满足这个等式。

把等式对C求和，每条边在两个端点之间最多被计算两次，于是

w(C)=∑v∈C∑e∋vye≤2∑eye≤2 OPT.w(C)=\sum_{v\in C}\sum_{e\ni v}y_e\le2\sum_e y_e\le2\,\mathrm{OPT}.

可行覆盖、对偶可行性、选中顶点紧性分别承担证明的一步。仅看到程序输出成本接近穷举最优，并不能替代这些不变量。

成本、证书与模型

保存每个顶点剩余预算、是否选中，以及每条边的对偶值，顺序扫描即可完成。初始化O(|V|+|E|)，每条边常数次算术与标记操作，总计O(|V|+|E|)次单位成本操作，额外空间O(|V|+|E|)，其中边预算数组是返回证书的一部分。

整数权下δ、slack和y始终是整数，不需要判断浮点数是否“足够接近零”。Python大整数加减比较的成本仍取决于输入位长；这里的线性界指操作次数。改用浮点数后，负的微小剩余预算可能破坏不变量，不能直接沿用精确证书判定。

外部验证器只需检查：C确实覆盖每条边；y非负；每个顶点关联预算和不超过其权重；以及w©≤2Σy。检查时不依赖算法内部slack数组，可以独立发现预算更新或索引错误。这个证书证明返回解距最优至多2倍，不声称找到了最优点覆盖。

整数间隙与算法偏差是两件事

单位权三角形需要至少两个顶点，OPT=2。给每个顶点x=1/2是分数可行解，成本3/2；对偶令每条边y=1/2也可行且同值，所以LP=3/2。整数间隙是OPT/LP=4/3，已经证明松弛未必精确。

推广到单位权完全图K_n，n≥2，整数最优为n−1；每个顶点取1/2得到LP≤n/2。每条边取y=1/(n−1)，每个顶点预算恰为1，给出LP≥n/2，所以间隙为2−2/n，趋近2。只依靠这个松弛值作为下界，不能保证一个对所有n都严格优于2的固定因子。

算法输出与整数最优的比值是另一种量。例如单条等权边，预算同时使两端变紧，全选策略成本2、最优1；而该图LP=OPT=1，整数间隙却为1。不能把算法的一次次优输出叫作LP的整数间隙。

负权不在模型内。零对偶向量甚至可能不满足负权顶点的约束，前面的初始化与弱对偶应用条件随之改变；实现应拒绝，不能默默运行。

可复跑检查

教学接口weighted_vertex_cover(weights, edges)返回按顶点编号排列的覆盖列表，以及与原始边一一对应的对偶价格列表。实现位于examples/advanced-algorithms/primal_dual_cover.py，允许平行边、拒绝自环和负权。

1
python3 examples/advanced-algorithms/check_primal_dual_cover.py

本轮实际检查238个穷举实例、1807个顶点子集；另检查固定种子20260920的200个随机实例、9048个子集。验证器从返回价格独立累计顶点预算，不读取内部slack，并与子集枚举最优值比较。

K₂到K₇的分数原始/对偶证书用Fraction精确核对，三角形得到LP=3/2、OPT=2。另有零权平行边边界、单边算法比值2而间隙1的区分，以及4个非法输入拒绝。结果保存在writing-plans/advanced-algorithms/evidence/primal-dual-cover-results.json；没有调用LP数值求解器，没有把这些有限实例当成一般近似证明。

练习

  1. 在三角形上把顶点权重设为1、2、3，按三种边顺序手算预算增加。逐个核对紧性、Σy≤OPT的下界证书与w©≤2Σy，比较输出是否相同。
  2. 对K_4写出整数最优覆盖、半整数原始解和等值对偶解。分别计算整数间隙，以及把所有x≥1/2顶点舍入后的实际近似比。

参考资料