Dual Fitting

证明模板 ​

对最小化问题写出线性规划松弛及其最大化对偶公理库线性规划对偶Linear programming duality · LP duality从线性约束生成对偶界，并以弱对偶、强对偶和互补松弛连接两侧最优解。。算法运行时为对象分配非负收费 $y$，先证明

$$\mathrm{ALG}\le \sum _j{y}_j$$

或与该和相等。原始 $y$ 可以违反对偶约束；若能证明每条约束左侧至多为右侧的 $\alpha$ 倍，则 $y/\alpha$ 对偶可行。由弱对偶，

$$\mathrm{ALG}\le \sum _j{y}_j=\alpha \sum _j(y_j/\alpha )\le \alpha \mathrm{OPT}.$$

Set Cover 收费例子 ​

Set Cover 对偶给每个元素变量 $y_e$，每个集合约束 $\sum _{e\in S}{y}_e\le c(S)$。贪心覆盖元素时的单位成本收费可能让某个集合约束超过 $c(S)$，但调和分析证明至多超出 $H_{|U|}$；除以该因子后成为可行对偶，重现贪心比率。

与 primal–dual 的差别 ​

经典 primal–dual 算法通常在运行中始终保持对偶可行，约束变紧时选原始对象；dual fitting 允许先“过度收费”，事后证明存在统一缩放。二者都用弱对偶，却有不同不变量。收费法若未写出具体对偶 LP 和违反因子，不能只因出现价格就称 dual fitting。

局部比率法有时产生同一个算法和近似常数，但它构造的是递归权重分解，而不是 LP 对偶证书。收费形式相似，不能代替对证明对象的辨认。

失败边界 ​

若各约束需要不同且无统一上界的缩放，无法得到全局 $\alpha$。最小/最大方向、对偶变量符号与弱对偶方向必须一致；把不可行对偶直接当 OPT 下界会反转证明。积分性 gap 可能限制该 LP 框架能证出的最好比率。

证书审计清单 ​

一份完整 dual-fitting 证明必须依次给出原始 LP 与对偶 LP、算法成本和收费总和的关系、所有对偶约束的统一违反上界，以及缩放后变量的符号合法性。只证明算法成本可以“分摊”给若干对象，还没有得到最优值下界；只检查算法选中的约束，也不能推出整个对偶解可行。

这套证书可以直接核对。以 Set Cover 为例，记录各元素收费 $y_e\ge 0$ 后，对每个非零成本集合计算

$${\rho }_S=\frac{\sum _{e\in S}{y}_e}{c(S)}.$$

取 $\alpha =\underset{S}{max}{\rho }_S$ 后，逐约束检查 $y/\alpha$ 可行，再核对 $\mathrm{ALG}\le \sum _e{y}_e$，便得到 $\alpha$ 的近似比公理库近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。。若某个 $c(S)=0$，应先把免费集合单独处理，否则比值没有定义；若 $\alpha$ 随实例规模无界，则这份收费仍可能正确，却没有给出有意义的统一近似保证。

参考资料

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