Dual Fitting

算法运行时产生的收费往往已经解释了 ALG 的成本，却未必满足每条对偶容量限制。Dual fitting 不强迫过程始终可行，而是度量最坏一条约束被挤爆了多少；若所有违反都能被同一个 $\alpha$ 控住，统一缩放便把这份运行轨迹变成合法的 OPT 下界证书。

图示采用单位右端的收费形式：某条集合约束收到 $6$，容量为 $4$，需要至少 $3/2$ 的缩放。完整证书必须让同一个因子覆盖所有集合约束，才能把最后一项作为最优值下界。

Set Cover 收费例子 ​

设有限全集 $U$ 非空，集合族能够覆盖 $U$，每个集合成本 $c(S)\ge 0$。先选入所有免费集合，并移去它们已覆盖的元素；这些元素收费为零。若已覆盖全部元素，就得到成本零的最优解。否则只需处理剩余实例中的正成本集合。

贪心每次选择“成本除以新覆盖元素数”最小的集合，把这个单位成本记为每个新覆盖元素的收费 $y_e$。每次所选集合的成本恰被它的新元素分摊，所以 $\mathrm{ALG}=\sum _e{y}_e$。对任意集合 $S$，按其元素被覆盖的先后编号；在还有 $q$ 个元素未覆盖时，贪心所选单位成本至多为 $c(S)/q$，因为 $S$ 本身也是候选。若一次同时覆盖多个元素，也可任意排列它们；各个对应分母只会减小，界仍成立。因此

Set Cover 对偶正是 $\sum _{e\in S}{y}_e\le c(S)$、$y_e\ge 0$，故统一除以 $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$ 后，对每个非零成本集合计算

取 $\alpha =max\{1,\underset{S}{max}{\rho }_S\}$ 后，逐约束检查 $y/\alpha$ 可行，再核对 $\mathrm{ALG}\le \sum _e{y}_e$，便得到 $\alpha$ 的近似比理路近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。。免费集合按前述步骤处理，以免除以零；没有剩余元素时直接报告零成本最优。若 $\alpha$ 随规模增长，应报告明确的函数界 $\alpha (n)$：例如 $H_n=O(\log n)$ 仍是有意义的近似保证，只是不是常数保证。