Deterministic 7/8-approximation for the metric maximum TSP
We 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 [L 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]. (C) 2009 Elsevier B.V. All rights reserved.
approximation the traveling salesman problem deterministic algorithm