Constant factor approximation for ATSP with two edge weights
成果类型：
Article
署名作者：
Svensson, Ola; Tarnawski, Jakub; Vegh, Laszlo A.
署名单位：
Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of London; London School Economics & Political Science
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-017-1195-7
发表日期：
2018
页码：
371-397
关键词：
摘要：
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.