A 5/8 Approximation Algorithm for the Asymmetric Maximum TSP
The Asymmetric Maximum Traveling Salesperson problem, also known as the Taxicab Ripoff problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with non-negative weights.
We propose a polynomial time
approximation algorithm for the problem with a 5/8 approximation guarantee.
This improves upon a chain of previous results with approximation guarantees ½ <4/7 <38/63 <8/13. These algorithms all
use a combinatorial algorithm to find a cycle cover, which is used to
approximate the tour. Our solution uses an LP instead, allowing additional
constraints helping to achieve the 5/8 approximation guarantee. We also make
use of the LP in a novel manner and strengthen the Path-Coloring Lemma
originally proposed by Kosaraju, Park and Stein (1996).