Improved approximation algorithms for metric MaxTSP
Improved approximation algorithms for metric MaxTSP
复制标题
DOI：
10.1007/s10878-006-9023-7
复制
发表时间：
2005-10
影响因子：
1
通讯作者：
Zhi-Zhong Chen;Takayuki Nagoya
中科院分区：
文献类型：
--
作者：
Zhi-Zhong Chen;Takayuki Nagoya
我们针对最大旅行商问题的度量情况提出了两种多项式时间近似算法。其中之一是有向图，其近似率为。另一种是无向图，其近似率为 。两种算法都比之前的最佳算法有所改进。
We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is. The other is for undirected graphs and its approximation ratio is. Both algorithms improve on the previous bests.