近似算法

在计算复杂性理论中的某些假设下，比如最著名的${\displaystyle P\neq NP}$假设下，对于一些可已被证明为NP完全的优化问题，无法在多项式时间内精确求到最优解，然而在现实或理论研究中，这类问题都有广泛的应用，在精确解无法得到的情况下，转而依靠高效的近似算法求可以接受的近似解。近似算法的研究也是当今计算机科学研究的一个主要方向。

对于一个最大化问题的实例，设其最优解是${\displaystyle OPT}$，某个近似算法的解是${\displaystyle x}$，若下式成立，

${\displaystyle \alpha \cdot OPT\leq x\leq OPT}$

其中${\displaystyle 0<\alpha <1}$则定义此近似算法的近似比为${\displaystyle \alpha }$。

相应的，对于一个最小化问题的实例，设其最优解是${\displaystyle OPT}$，某个近似算法的解是${\displaystyle x}$，若下式成立，

${\displaystyle OPT\leq x\leq \alpha \cdot OPT}$

其中${\displaystyle \alpha >1}$则定义此近似算法的近似比为${\displaystyle \alpha }$。

按照可以达到近似比的不同，可以将近似算法大致按以下分类：

1. FPTAS
2. PTAS
3. 常数近似
4. 对数的多项式
5. 多项式

其中对数的多项式和多项式都是对应于输入规模的。

近似算法的常用设计方法有贪心法，线性规划、半正定规划的松弛和取整，随机算法等。

对于一些问题，近似算法的近似比也会有一定的局限性，一个最大化问题（最小化问题类似）最好的近似算法可以达到的近似比不能比某个特定的值更高。20世纪90年代发展起来的PCP理论为证明近似的困难性提供了一套系统的工具。例如，对于常见的MAX3SAT问题，一个简单的随机算法可以满足7/8的子句，但是可以证明，找到一个能保证满足高于${\displaystyle 7/8+\epsilon (\forall \epsilon >0)}$比例子句的问题是NP困难的。所以在${\displaystyle P\neq NP}$的假设下，这个问题我们可以得到的最优近似比是7/8。进入21世纪之后，计算机科学家为了近似困难性更往前一步，提出了唯一性游戏假设，在这一假设下，一些重要的问题如MAX-CUT、MAX2SAT也被证明了可能达到的最优近似比。

• P/NP問題