2020/05/21 by Paluch, Katarzyna
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2005.10800
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 (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+(11(1-α))/(9-2α))-approximation algorithm for the shortest superstring problem (SSP), we obtain also a (2 (33)/(76) ≈ 2,434)-approximation algorithm for SSP, beating the previously best known (having an approximation factor equal to 2 (11)/(23) ≈ 2,4782.)