Constant factor approximation for ATSP with two edge weights
Constant factor approximation for ATSP with two edge weights
复制标题
具有两个边权重的 ATSP 的常数因子近似
DOI：
--
复制
发表时间：
2015
影响因子：
2.7
通讯作者：
László A. Végh
中科院分区：
文献类型：
--
作者：
O. Svensson;Jakub Tarnawski;László A. Végh
给出了具有两个不同边权的有向图的最短路度量上非对称旅行商问题的一个恒因子逼近算法。对于单位边权的情况，Svensson最近给出了第一个恒定因子近似。这是通过引入一个更简单的称为局部连通性ATSP的问题来实现的，并证明了这个问题的良好解决方案可以用来获得ATSP的常因子近似。本文求解了两种不同边权的局部连通性ATSP问题。该解基于Hold-Karp松弛解的流动分解定理，它可能是独立感兴趣的。
We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held–Karp relaxation, which may be of independent interest.