或者更确切地说，组合算法和线性算法的定义分别是什么？
澄清一下，因为显然第一响应者误解了这个问题:我不是在寻找在线性时间与非线性时间中运行的算法的定义。线性算法在某种程度上与线性规划相关，线性规划是一种用于寻找或近似线性优化问题的解决方案的技术。
由于 NP-hard 问题太难了，整个领域都在试图找到近似解。例如，旅行商问题有几个近似解，它们在多项式时间内运行，并产生一个在最佳解的给定范围内的解。
其中一些近似算法称为线性算法，另一些称为组合算法；后者似乎更受欢迎(为什么？)。这是我想了解的两个概念。
最佳答案
问题是问题表述之一。
正如你所说的旅行商问题 (TSP) 是 NP-hard 正是因为它有一个离散的问题表述(销售人员要么访问一个城市，要么不在特定时间访问)。这个离散公式提出了问题，它的算法，组合 . (请注意，并非所有组合问题都是 NP 难题；请考虑排序算法。)
然而，TSP 的线性规划 (LP) 松弛导致 线性 算法。这是因为问题已被重新表述，使得销售人员在一定比例的时间内访问一个城市。使用 LP 松弛的主要原因是因为松弛版本可以在 中解决。多项式时间。但是，LP松弛的解决方案不一定是原始问题的解决方案。
关于np-complete - 'combinatorial algorithm' 和 'linear algorithm' 之间有什么区别？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1002697/