对于最小化算法来说是 2-近似意味着什么？

对于最小化问题，保证是 $C \leq \rho(n) \cdot C^*$。对于最大化问题，它是 $C \geq \frac{C^*}{\rho(n)}$。

适用条件：C 是算法产生的成本。；C* 是真实的最佳成本。；rho(n) 是近似界限。

这四种技术是贪心策略、线性规划松弛和舍入、原始-对偶方案以及局部搜索。

适用条件：适用于为 NP 难问题设计近似算法。

为 NP 难优化问题寻找精确解需要指数时间，如 $O(2^n)$ 或 $O(n!)$，这对于大型输入在计算上是不可行的。

适用条件：问题是 NP 难优化问题；寻求精确解

FPTAS 和 PTAS 允许任意接近的近似。APX 允许恒定因子近似。

适用条件：比较优化问题的标准近似类。

近似界限是一个保证的乘法限制，规定了在最坏情况下算法的结果比真实最优解差多少。

适用条件：用于最小化或最大化问题。；表示相对于最优解的最坏情况保证。