Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman
Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman
复制标题
二标准度量旅行商的改进和去随机近似
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Witek
中科院分区：
文献类型：
--
作者：
Christian Glaßer;Christian Reitwießner;M. Witek
对两准则旅行商问题(2-TSP)最著名的近似算法进行了改进和去随机化。更准确地说，我们构造了一个确定性的2-近似，它回答了Manthee提出的一个公开问题。此外，我们证明了2-TSP是随机化的(3=2+“；2)-可逼近的，并且我们给出了两准则旅行商路径问题2-TSPP、2-TSPP和2-TSPPst的第一个随机化近似。我们进一步证明了改进我们的随机化近似算法的难度，因为这样的改进迫使我们改进TSP、TSPP和TSPPst(Christodes)的最已知的近似
We improve and derandomize the best known approximation algorithm for the twocriteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey. Moreover, we show that 2-TSP is randomized (3=2 + "; 2)-approximable, and we give the rst randomized approximations for the two-criteria traveling salesman path problems 2-TSPP, 2-TSPPs, and 2-TSPPst. We further provide arguments that indicate the hardness of improving our randomized approximation algorithms in the sense that such improvements force us to improve the best known approximations for TSP, TSPPs, and TSPPst (Christodes