Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring

Abstract

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{3}{4}$-approximation algorithm for Max ATSP. It is based on a novel use of {\it half-edges}, matchings and a new method of edge coloring. (A {\it half-edge} of edge $(u,v)$ is informally speaking "either a head or a tail of $(u,v)$".) The current best approximation algorithms for Max ATSP, achieving the approximation guarantee of $\frac{2}{3}$, are due to Kaplan, Lewenstein, Shafrir and Sviridenko and Elbassioni, Paluch, van Zuylen. Using a recent result by Mucha, which states that an $\alpha$-approximation algorithm for Max ATSP implies a $(2+\frac{11(1-\alpha )}{9-2\alpha })$-approximation algorithm for the shortest superstring problem (SSP), we obtain also a $(2\frac{11}{30}\approx 2,3667)$-approximation algorithm for SSP, beating the previously best known (having approximation factor equal to $2\frac{11}{23}\approx 2,4782$.)

Cited by in corpus (3)

• Approximation of the Double Travelling Salesman Problem with Multiple Stacks
• Greedy Shortest Common Superstring Approximation in Compact Space
• On improving the approximation ratio of the r-shortest common superstring problem