MATCHING SUPPLEMENT APPLICATION FOR SOLVING MAX TSP

An approach to approximation solving of MAX TSP based on supplementation of partial tours by matchings of the open vertexes subgraphs is presented in the paper. Analytical research demonstrates that this algorithm firstly have time complexity no more than $O(n^3)$, here $n$ is the number of towns, and secondly does not improve the guaranteed accuracy ratio of the known algorithms. The modification of Serdukov algorithm with time complexity $O(n^3)$ and best known guaranteed accuracy ratio is presented. Computational experiment results cause to anticipate asymptotic accuracy of this algorithm for a broad spectrum of MAX TSP.

Keywords

Hamilton cycle, travelling salesman problem, approximation algorithm, approximation ratio, matching, time complexity, computational experiment