P-Complete Approximation Problems
P-Complete Approximation Problems
复制标题
DOI：
10.1145/321958.321975
复制
发表时间：
1976-07
期刊：
影响因子：
--
通讯作者：
S. Sahni;T. Gonzalez
中科院分区：
文献类型：
--
作者：
S. Sahni;T. Gonzalez
对于旅行推销员、周期覆盖、0-1整数规划、多商品网络流、二次分配等p完全问题，证明了逼近问题也是p完全的。在此基础上，提出了一种求解聚类问题的线性时间逼近算法。
For P-complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is also P-complete. In contrast with these results, a linear time approximation algorithm for the clustering problem is presented.