An improved approximation algorithm for the maximum TSP
In this paper, we consider the maximum traveling salesman problem with gamma-parameterized triangle inequality for gamma is an element of [1/2, 1), which means that the edge weights in the given complete graph G = (V, E, w) satisfy w(uv) <= gamma . (w(ux) + w(xv)) for all distinct nodes u, x, v is an element of V. For the maximum traveling salesman problem with gamma-parameterized triangle inequality, R. Hassin and S. Rubinstein gave a constant factor approximation algorithm with polynomial running time, they achieved a performance ratio gamma only for gamma is an element of [1/2, 5/7) in [8], which is the best known result. We design a k gamma+1-2 gamma/k gamma-approximation algorithm for the maximum traveling salesman problem with gamma-parameterized triangle inequality by using a similar idea but very different method to that in [11], where k = min{vertical bar C(i)vertical bar vertical bar i = 1, 2, ..., m}, C(1), C(2), ..., C(m) is an optimal solution of the minimum cycle cover in G, which is better than the gamma-approximation algorithm for almost all gamma is an element of [1/2, 1). (C) 2010 Elsevier B.V. All rights reserved.
approximation algorithm maximum traveling salesman problem parameterized triangle inequality