Deterministic 7/8-approximation for the metric maximum TSP (Q1034619)

The authors present the first deterministic 7/8-approximation algorithm for the maximum traveling salesman problem (MAX-TSP) in complete metric graphs. The first approach is based on a maximum cycle cover: the lightest edge in each cycle is removed, while the actual set of paths is enlarged by certain edges to get a Hamiltonian cycle. The second approach processes the cycles of an maximum cycle cover in a certain order, which is based on so-called loose-ends (vertices), and determines certain heavy edges, which are added successively to a maximum matching resulting finally in a Hamiltonian cycle. The heavier of both resulting Hamiltonian cycles gives a 7/8 approximation guarantee in case of graphs with an even number of vertices. For an odd number of vertices a (perhaps avoidable) overhead of \(O(n^4)\) in the time complexity -- induced by matching-cover pairs -- is a significant drawback for practical use.