原始—对偶方法

原始解给出可实现方案，对偶解给出任何方案都不能突破的界。原始—对偶方法不先完整求出原问题再检查对偶，而是在构造原始可行解的同时提升对偶变量；当某些约束变紧时，算法据此选择原始对象，最终用互补松弛或近似版本比较两边成本。两者相遇时就得到可验证的最优性。对偶变量常可解释为资源价格，价格上涨直到某个选择“付得起”。

匈牙利算法维护顶点势与紧边匹配；最短路和最小费用流也可用势函数解释。仅写出一个对偶变量并不构成算法，必须说明如何更新和为何终止。原始—对偶内点法理路原始—对偶内点法Primal-dual interior-point method · Primal-dual path following对原始可行性、对偶可行性与扰动互补条件联合取 Newton 步，以保正步长推进，并区分互补量与真正的可行对偶间隙。给出连续优化中的具体实现：联合线性化原始、对偶和互补残差，再用保正步长更新；它不同于下面逐边抬价、在顶点约束变紧时选点的组合构造。对整数规划，分数原始解与 LP 对偶相等只证明松弛最优；若相等的原始解本身整数可行，则同时证明整数最优。

顶点覆盖：从抬价到证书 ​

给无向图每个顶点一个非负权重 $w_v$，选点集 $S$ 使每条边至少有一个端点入选。其 LP 对偶给每条边 $e$ 一个非负价格 $y_e$，要求每个顶点的负载 $\sum _{e\ni v}{y}_e\le w_v$，目标为最大化 $\sum _e{y}_e$。

从 $y=0,S=\varnothing$ 开始，选一条尚未覆盖的边 $uv$，把 $y_{uv}$ 增加两个端点剩余预算的较小值。至少一个端点于是变紧，把这样的端点加入 $S$；预算已为零时直接选点即可。每步新增顶点，至多 $|V|$ 步结束。后续只抬未覆盖边的价格，故不会再改变已选顶点的负载。

例如路径 a—b—c，权重分别为 2、3、2。先把边 ab 的价格升到 2，选入 a；再把 bc 的价格升到 1，b 的总负载变为 3，选入 b。所得覆盖成本为 5，对偶总价为 3，且每个顶点都没有超预算。只选 b 的成本为 3，说明过程不一定精确最优。

对一般输出，每个已选顶点都保持变紧，于是 $\sum _{v\in S}{w}_v=\sum _{v\in S}\sum _{e\ni v}{y}_e\le 2\sum _e{y}_e\le 2OP{T}_{int}.$ 中间的 2 来自每条边最多被两个已选端点计费；最后一步来自对偶可行性。这样，可行覆盖与合法下界共同给出可检查的 2-近似证书，无须先把 LP 完整求到最优。

原始可行、对偶可行与互补松弛三者必须分清；只让目标值接近却违反约束，不构成证书。整数问题的 LP 对偶可能有 integrality gap，因此原始—对偶算法常给近似而非精确解。

该框架统一匹配、覆盖与流算法，也出现在设施选址和网络设计的近似方案中，常能同时产生构造解、对偶下界和近似比证明。不同问题里“价格变紧”对应的对象并不相同：可以是匹配边、被覆盖约束、流的势，或开放设施与连接客户的费用，因此仍须逐题证明可行性和计费关系。对偶拟合理路Dual Fittingdual fitting · 对偶拟合法从算法收费构造可能不可行的对偶解，再统一缩放为可行下界证书。允许构造过程中暂时得到不可行对偶，再按统一因子缩放成合法下界；Christofides 算法理路Christofides 算法Christofides algorithm用 MST、奇度点最小完美匹配和 Euler shortcut 构造 metric TSP 的 3/2 近似。则把 MST 与最小权完美匹配组合成度量 TSP 的 $3/2$-近似，其下界与奇度修补分析不等同于逐约束抬价。

Goemans–Williamson Max-Cut理路Goemans–Williamson Max-Cut 近似Goemans-Williamson Max-Cut · GW algorithm · Max-Cut SDP rounding以单位向量半正定松弛和随机过原点超平面舍入无向非负权 Max-Cut，并由逐边角度不等式得到 0.87856 期望近似比。先解 SDP 松弛，再做随机超平面舍入，近似比来自角度概率与松弛值，而不是线性互补松弛。packing/covering 线性规划中，乘法权重更新理路乘法权重更新方法multiplicative weights update · MWU以指数方式降低高损失动作的权重，并用总权重势函数给出累计性能保证。又可通过可分离 oracle 调整权重。原始—对偶、对偶拟合、SDP 舍入和乘法更新都借助下界证书，但其可行性不变量、随机性和保证类型必须分别陈述。