2014/01/15 by Katarzyna Paluch, Paluch, Katarzyna
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1401.3670
arxiv created 2014/01/15 · openalex publication_date 2014/01/15 · arxiv updated 2014/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 34-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 23, are due to Kaplan, Lewenstein, Shafrir and Sviridenko and Elbassioni, Paluch, van Zuylen. Using a recent 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 (11)/(30) ≈ 2,3667)-approximation algorithm for SSP, beating the previously best known (having approximation factor equal to 2 (11)/(23) ≈ 2,4782.)