APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS
APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS
复制标题
DOI：
10.1016/s0022-0000(74)80044-9
复制
发表时间：
1974-01-01
影响因子：
1.1
通讯作者：
JOHNSON, DS
中科院分区：
文献类型：
--
作者：
JOHNSON, DS
简单的，多项式时间，启发式算法找到近似的解决方案，以各种多项式完全优化问题进行了分析，就其最坏的情况下的行为，衡量的最坏的解决方案的值，可以选择的算法的最佳值的比率。对于某些问题，例如简单形式的背包问题和基于可满足性测试的优化问题，存在这样的算法，其比率由常数限定，与问题大小无关。对于一些集合覆盖问题，简单的算法产生的最坏情况下的比率，可以增长的问题大小的日志。对于在图中寻找最大团的问题，没有找到比增长至少不快于0（nε）的算法，其中n是问题大小，ε> 0取决于算法。
Simple, polynomial-time, heuristic algorithms for finding approximate solutions to various polynomial complete optimization problems are analyzed with respect to their worst case behavior, measured by the ratio of the worst solution value that can be chosen by the algorithm to the optimal value. For certain problems, such as a simple form of the knapsack problem and an optimization problem based on satisfiability testing, there are algorithms for which this ratio is bounded by a constant, independent of the problem size. For a number of set covering problems, simple algorithms yield worst case ratios which can grow with the log of the problem size. And for the problem of finding the maximum clique in a graph, no algorithm has been found for which the ratio does not grow at least as fast as 0(nε), where n is the problem size and ε> 0 depends on the algorithm.