A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP
A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP
复制标题
最大非对称TSP的5/8近似算法
DOI：
--
复制
发表时间：
2004
影响因子：
0.8
通讯作者：
M. Sviridenko
中科院分区：
文献类型：
--
作者：
Moshe Lewenstein;M. Sviridenko
最大的不对称旅行销售人员问题，也称为出租车撕裂问题，是在完整的不对称图中找到最大加权旅行的问题。
我们提出了一个具有5/8近似保证的问题的多项式时间近似算法。 （1）改善了先前结果的近似因素，并且（2）为先前涉及的算法提供了更简单的解决方案。我们的解决方案使用简单的线性编程公式。先前的解决方案是组合。我们以新颖的方式利用线性编程，并加强[S. S. R. Kosaraju，J。K。Park和C. Stein，《漫长的旅行和短期》，在第35届年度IEEE计算机科学基础研讨会论文集，1994年，第166---177页。
The maximum asymmetric traveling salesperson problem, also known as the taxicab rip-off problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with nonnegative weights.
We propose a polynomial time approximation algorithm for the problem with a 5/8 approximation guarantee. This (1) improves upon the approximation factors of previous results and (2) presents a simpler solution to the previously fairly involved algorithms. Our solution uses a simple linear programming formulation. Previous solutions were combinatorial. We make use of the linear programming in a novel manner and strengthen the path-coloring method originally proposed in [S. R. Kosaraju, J. K. Park, and C. Stein, Long tours and short superstrings, in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 166--177].