Improved deterministic approximation algorithms for Max TSP
We present an O(n(3))-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 61/81, where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n(3))-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically 17/20. Both algorithms improve on the previous bests. (c) 2005 Elsevier B.V. All rights reserved.
approximation algorithms graph algorithms randomized algorithms