近似算法

近似算法面向优化问题：在满足约束的可行解中，希望找到代价尽量小或收益尽量大的解。对于许多难以高效精确求解的问题，可以退而要求多项式时间算法返回有质量保证的解。保证来自对所有适用输入的分析，而不只是测试数据上的良好成绩。

以非负目标为例，若采用α≥1的约定，最小化问题要求算法代价不超过α倍最优代价；最大化问题则要求最优收益不超过α倍算法收益。另一种最大化约定直接使用不超过1的保证比例。谈近似比必须先交代方向和约定，不能把“2近似”理解成误差仅有两个单位。

参考：[1]

无权最小顶点覆盖要求选出尽量少的顶点，让每条边至少有一个端点入选。一个简单算法不断取尚未被处理的边，把两个端点都加入答案，并删去与它们关联的边，直到没有剩余边。所取边互不共享端点，组成极大匹配；这里的“极大”只是不再能加边，并不要求边数最多。

所有边都被选出的端点覆盖，所以答案可行。若匹配有m条边，任何顶点覆盖至少要为每条匹配边选一个端点，且这些端点不能重复使用，因此最优解至少有m个顶点。算法选了2m个，故不超过最优的两倍。证明不需要知道真正的最优值，也不保证每次恰好差一倍。

参考：[1]

近似方案把精度参数ε纳入讨论。对最小化问题，多项式时间近似方案PTAS为每个固定正ε提供不超过最优值(1＋ε)倍的可行解，运行时间对输入编码长度为多项式；但对ε的依赖可能很差。例如指数中含有1/ε的时间界，仍可能符合PTAS定义。

完全多项式时间近似方案FPTAS要求时间同时对输入长度和1/ε为多项式。它给出更严格的效率承诺，但不意味着把ε设为0就能得到多项式时间精确算法。输入长度还应按位数计算：一个算法若时间正比于某个很大的输入整数，其时间未必对该整数的二进制编码长度为多项式。

参考：[2]

近似比依赖问题的完整定义。上面的顶点覆盖证明使用无权目标；若给顶点不同权重，直接选一条边的两个端点就不能照搬原有成本分析。改变约束、允许不可行输出，或者换用另一种目标函数，都需要重新证明保证。

近似算法也不等于把小数截断。舍入可以是构造算法的技术，例如压缩背包问题的收益尺度，但必须同时控制可行性和目标损失。没有最坏情形质量界的启发式方法可能很好用，却不能仅凭经验表现获得同样的保证；一个有界近似算法也仍需结合数据规模与实际开销评估用途。

参考：[1] [2]