An improved approximation algorithm for the maximum TSP

Abstract: 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 satisfy for all distinct nodes . 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 , 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 , where is an optimal solution of the minimum cycle cover in , which is better than the -approximation algorithm for almost all . [Copyright &y& Elsevier]