Complexity and Approximation
Complexity and Approximation
复制标题
DOI：
10.1007/978-3-642-58412-1
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
G. Ausiello;A. Marchetti-Spaccamela;P. Crescenzi;G. Gambosi;M. Protasi;V. Kann
中科院分区：
文献类型：
--
作者：
G. Ausiello;A. Marchetti-Spaccamela;P. Crescenzi;G. Gambosi;M. Protasi;V. Kann
在计算机应用中，我们习惯于近似。事实上，在许多情况下，近似值的概念各不相同。一个值得注意的例子是在数值分析或计算几何中出现的近似类型，因为我们不能以任意精度进行计算，我们必须截断真实的数的表示。在其他情况下，我们用简单的数学对象来近似复杂的数学对象：例如，我们有时用分段线性函数来表示非线性函数。需要解决困难的优化问题是迫使我们处理近似的另一个原因。特别是，当一个问题在计算上是困难的（即，我们知道解决它的唯一方法是使用一个在指数时间内运行的算法），它可能实际上是不可行的，因为它可能需要几个月或几年的机器时间，即使在强大的并行计算机的帮助下。在这种情况下，我们可以决定限制自己计算一个解决方案，虽然不是最优的，但仍然接近最优，并可以在多项式时间内确定。我们称这种类型的解决方案的近似解决方案和相应的算法多项式时间近似算法。实际上，在上述意义上，大多数具有很大实际意义的组合优化问题在计算上是难以处理的。在形式上，它们被归类为NP-难优化问题。
N COMPUTER applications we are used to live with approximation. Var I ious notions of approximation appear, in fact, in many circumstances. One notable example is the type of approximation that arises in numer ical analysis or in computational geometry from the fact that we cannot perform computations with arbitrary precision and we have to truncate the representation of real numbers. In other cases, we use to approximate com plex mathematical objects by simpler ones: for example, we sometimes represent non-linear functions by means of piecewise linear ones. The need to solve difficult optimization problems is another reason that forces us to deal with approximation. In particular, when a problem is computationally hard (ie, the only way we know to solve it is by making use of an algorithm that runs in exponential time), it may be practically unfeasible to try to compute the exact solution, because it might require months or years of machine time, even with the help of powerful parallel computers. In such cases, we may decide to restrict ourselves to compute a solution that, though not being an optimal one, nevertheless is close to the optimum and may be determined in polynomial time. We call this type of solution an approximate solution and the corresponding algorithm a polynomial-time approximation algorithm. Most combinatorial optimization problems of great practical relevance are, indeed, computationally intractable in the above sense. In formal terms, they are classified as Np-hard optimization problems.