近似算法基础

最优解

经常用 $OPT_{n}(I)$ 表示关于实例 $I \in D_{\pi}$ 的最优解解值 $M_{n}\left(I, S^{*}\right)$。

在不引起混淆的情况下，通常将实例 $I$ 的最优解的解值记为 $O P T(I)$ 。 假设算法 $A,$ 对于问题 $\pi$ 的任意实例 $I \in D_{\pi}$, 都可找到相应的可行解 $S \in S_{n}(I),$ 其解值为 $M_{n}(I,S)$。

令 $A(I)=M_{n}(I, S),$ 若对于所有实例 $I \in D_{\pi},$ 都有 $A(I)=O P T(I)$， 则称算法 $A$ 为解答问题 $\pi$ 的精确算法。

否则, 算法 $A$ 所求出解的解值达不到最优解, 即 $A(I) \neq O P T(I)$, 则称算法 $A$ 为解答问题 $\pi$ 的近似算法。

绝对近似算法

给定优化问题 $\pi,$ 若有算法 $A,$ 存在一个常数 $K \geqslant 0,$ 使得对于所有实例 $I \in D_{\pi},$ 总有

$|A(I)-O P T(I)| \leqslant K$

则称算法 $A$ 为解答问题 $\pi$ 的绝对近似算法；若 $A$ 为多项式时间算法，则称 $A$ 为解答问 题 $\pi$ 的多项式时间绝对近似算法。