原始—对偶方法

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

匈牙利算法维护顶点势与紧边匹配；最短路和最小费用流也可用势函数解释。仅写出一个对偶变量并不构成算法，必须说明如何更新和为何终止。对整数规划，线性对偶相等通常只证明松弛最优，不能自动证明整数解最优。

加权顶点覆盖的 LP 对偶是边打包：逐步提高未覆盖边的对偶变量，直到某个端点的对偶负载达到其权重，就选入该顶点。最终每条边被覆盖，而所选顶点权重可由相邻对偶值计费，得到经典 $2$-近似分析。

原始可行、对偶可行与互补松弛三者必须分清；只让目标值接近却违反约束，不构成证书。整数问题的 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 舍入和乘法更新都借助下界证书，但其可行性不变量、随机性和保证类型必须分别陈述。