What is Approximation Ratio?

Approximation Ratio

近似比率是用来衡量一个算法找到的近似解与最优解之间的差距的一个量化指标.

假设有一个优化问题，其最优解的值是OPT，用时间T，而我们的算法得到的解的值是ALG,用时间t。如果算法有一个2的近似比率，那么我们可以保证ALG ≤ 2 * OPT and t ≤ 2 * T。这意味着算法找到的解的“成本（时间）”和“答案”不会超过最优解的两倍。