论文标题
新的近似算法，最大不对称的旅行推销员和最短的超音
New Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring
论文作者
论文摘要
在最大的不对称旅行推销员问题（MAX ATSP）中，我们获得了一个完整的定向图，边缘上有非负重的权重，我们希望计算一次旅行推销员的最大权重。在本文中，我们给出了一个快速组合$ \ frac {7} {10} $ - Max Atsp的近似算法。它基于{\ em消除}和{\ em稀释}有问题的子图的技术，并借助{\ it half-it half-edges}和一种边缘着色方法。 （一个{\ it Half-itge}的边缘$（u，v）$是非正式地说：“ $（u，v）$的头或尾巴的尾巴。 当前最佳ATSP的最佳近似算法获得了$ \ frac 23 $的近似保证，这是由于Kaplan，Lewenstein，Shafrir，Sviridenko（2003）和Elbassioni，Paluch，Paluch，van Zuylen（2012）。使用Mucha的结果，该结果指出，最大ATSP的$α$ - APPRXIMATION算法意味着$（2+ \ frac {11（1-α）} {9-2α}）$ - 近似算法的近似算法，用于最短的supperString问题（SSP），我们还获得了$（2 2,434）$ - SSP的近似算法，击败以前最著名的（具有等于$ 2 \ frac {11}} {23} {23} \ 2,4782 $的近似因子。
In the maximum asymmetric traveling salesman problem (Max ATSP) we are given a complete directed graph with nonnegative weights on the edges and we wish to compute a traveling salesman tour of maximum weight. In this paper we give a fast combinatorial $\frac{7}{10}$-approximation algorithm for Max ATSP. It is based on techniques of {\em eliminating} and {\em diluting} problematic subgraphs with the aid of {\it half-edges} and a method of edge coloring. (A {\it half-edge} of edge $(u,v)$ is informally speaking "either a head or a tail of $(u,v)$".) A novel technique of {\em diluting} a problematic subgraph $S$ consists in a seeming reduction of its weight, which allows its better handling. The current best approximation algorithms for Max ATSP, achieving the approximation guarantee of $\frac 23$, are due to Kaplan, Lewenstein, Shafrir, Sviridenko (2003) and Elbassioni, Paluch, van Zuylen (2012). Using a result by Mucha, which states that an $α$-approximation algorithm for Max ATSP implies a $(2+\frac{11(1-α)}{9-2α})$-approximation algorithm for the shortest superstring problem (SSP), we obtain also a $(2 \frac{33}{76} \approx 2,434)$-approximation algorithm for SSP, beating the previously best known (having an approximation factor equal to $2 \frac{11}{23} \approx 2,4782$.)
