Improved deterministic approximation algorithms for Max TSP

We present an O(n3)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 6181, where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n3)-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically 1720. Both algorithms improve on the previous bests.