Improved approximation algorithms for metric MaxTSP (Q2467566)

The paper deals with approximation solving techniques for the maximum travelling salesman problem. Two different cases of this problem are considered here. The first case of the problem is defined on a complete directed graph and the second one is formulated on an undirected complete graph. The both graphs are weighted and it is assumed that the nonnegative weights satisfy the triangle inequality. The authors developed two different algorithms following differences between the cases and also the different approaches to their solving used by preceding researchers. The authors based their approach to the first case of a problem on the Kaplan's algorithm based on computing two cycle covers of the input graph and on their further adjustment, result of which is a Hamiltonian cycle. The original Kaplan's algorithm yields a result, which reaches 10/13 of an optimal objective function value. The new algorithm developed by the authors improves one of the partial Kaplan's solutions by series of adjustments and it produces results, approximation ratio of which is 27/35. On the contrary to the first case of the asymmetric maximum salesman problem, the authors' approach to the second symmetric case is based on Hassin and Rubinstein's idea of generating a sequence of perfect matching, which is used in their randomized algorithm for the construction of a resulting solution. The expected approximation ratio of the original Hassin and Rubinstein's algorithm is 7/8-o(1). The authors suggested a new derandomized algorithm, which yields a result with the approximation ratio 7/8-o(1).