Deterministic 7/8-approximation for the metric maximum TSP

AbstractWe present the first 7/8-approximation algorithm for the maximum Traveling Salesman Problem (MAX-TSP) with triangle inequality. Our algorithm is deterministic. This improves over both the randomized algorithm of Hassin and Rubinstein [R. Hassin, S. Rubinstein, A 7/8-approximation algorithm for metric Max TSP, Inf. Process. Lett. 81 (5) (2002) 247–251] with an expected approximation ratio of 7/8−O(n−1/2) and the deterministic (7/8−O(n−1/3))-approximation algorithm of Chen and Nagoya [Z.-Z. Chen, T. Nagoya, Improved approximation algorithms for metric max TSP, in: Proc. ESA’05, 2005, pp. 179–190].In the new algorithm, we extend the approach of processing local configurations using the so-called loose-ends, which we introduced in [Ł. Kowalik, M. Mucha, 35/44-approximation for asymmetric maximum TSP with triangle inequality, in: Proc. 10th Workshop on Algorithms and Data Structures, WADS’07, 2007, pp. 590–601]