The approximability of NP-hard problems
The approximability of NP-hard problems
复制标题
NP 困难问题的近似性
DOI：
10.1145/276698.276784
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Sanjeev Arora
中科院分区：
文献类型：
--
作者：
Sanjeev Arora
组合优化中的许多问题都是NP难的（见[60]）。这迫使研究人员探索处理NP完全性的技术。一些人已经考虑了解决“典型”或“平均”实例而不是最坏情况实例的算法[86，100]。然而，在实践中，确定“典型”实例并不容易。其他研究人员试图设计近似算法。一个算法对于一个最大化问题达到一个近似比α，如果对于每个实例，它产生一个值至少为OPT/α的解，其中OPT是最优解的值。(For一个最小化问题，达到一个比率α需要找到一个解决方案的成本最多αOPT。）注意，根据定义，近似比≥ 1。经过25年的研究，近似算法是一个具有深度技术的主要研究领域（详细调查见[75]）。然而，研究人员未能为各种各样的NPhard优化问题设计出良好的近似算法。复杂性理论的最新发展--特别是在概率可检验证明（probabilistically checkable proofs，PCP）领域--提出了这种失败的原因：对于许多NP难问题，包括MAX-CLIQUE、CHROMATIC NUMBER、MAX-3SAT和SET-COVER，获得某些合理的近似比并不比计算最优解更容易。换句话说，近似是NP难的。这些负面
Many problems in combinatorial optimization are NP-hard (see [60]). This has forced researchers to explore techniques for dealing with NP-completeness. Some have considered algorithms that solve “typical” or “average” instances instead of worst-case instances [86, 100]. In practice, however, identifying “typical” instances is not easy. Other researchers have tried to design approximation algorithms. An algorithm achieves an approximation ratio α for a maximization problem if, for every instance, it produces a solution of value at least OPT/α, where OPT is the value of the optimal solution. (For a minimization problem, achieving a ratio α involves finding a solution of cost at most αOPT .) Note that the approximation ratio is ≥ 1 by definition. After twenty-five years of research, approximation algorithms is a major research area with deep techniques (see [75] for a detailed survey). Nevertheless, researchers have failed to design good approximation algorithms for a wide variety of NPhard optimization problems. Recent developments in complexity theory —specifically, in the area of probabilistically checkable proofs or PCPs— suggest a reason for this failure: for many NP-hard problems, including MAX-CLIQUE, CHROMATIC NUMBER, MAX-3SAT, and SET-COVER, achieving certain reasonable approximation ratios is no easier than computing optimal solutions. In other words, approximation is NP-hard. These negative