近似算法

近似算法是计算机科学中算法研究的一个重要方向。所谓“近似”，就是指结果不一定是最优的，但是也在可以承受的范围内，而且可以比精确求解消耗更少的资源。这里的资源是计算复杂性理论中的标准，可以是时间，空间或者询问次数等。

背景

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

近似比

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

$\alpha\cdot OPT\le x\le OPT$

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

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

$OPT\le x\le \alpha\cdot OPT$

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

分类

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

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

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

设计方法

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

近似的困难性

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