Improved approximation algorithms for metric MaxTSP
We present two polynomial-time approximation algorithms for the metric case of the maximum traveling salesman problem. One of them is for directed graphs and its approximation ratio is 27/35. The other is for undirected graphs and its approximation ratio is 7/8 - o(1). Both algorithms improve on the previous bests.
approximation algorithms tsp max tsp metric max tsp randomized algorithms derandomization