An improved approximation algorithm for the maximum TSP

In this paper, we consider the maximum traveling salesman problem with γ-parameterized triangle inequality for , which means that the edge weights in the given complete graph G=(V,E,w) satisfy w(uv)≤γ⋅(w(ux)+w(xv)) for all distinct nodes u,x,v∈V. For the maximum traveling salesman problem with γ-parameterized triangle inequality, R. Hassin and S. Rubinstein gave a constant factor approximation algorithm with polynomial running time, they achieved a performance ratio γ only for in [8], , which is the best known result. We design a -approximation algorithm for the maximum traveling salesman problem with γ-parameterized triangle inequality by using a similar idea but very different method to that in [11], where k=min{|Ci|∣i=1,2,…,m},C1,C2,…,Cm is an optimal solution of the minimum cycle cover in G, which is better than the γ-approximation algorithm for almost all .