Cycles merging algorithm for metric maximum traveling salesman problem

A. V. Panyukov ; Yu. F. Leonova

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 10 (2021) no. 4, pp. 26-36

Résumé

The traveling salesman problem is an important combinatorial optimization problem that involves finding the optimal path between given vertices. The maximum traveling salesman problem has several practical applications, for example, when compressing arbitrary data and analyzing DNA sequences. Even though maximum traveling salesman problem is less developed than minimum traveling salesman problem, there are effective approximate algorithms for solving this problem. The article presents estimates of the accuracy of the best algorithms for the approximate solution of the metric maximum traveling salesman problem. The paper proposes a new algorithm for the approximate solution of the traveling salesman problem to the maximum, consisting of finding the 2-factor of the extreme weight in each graph, and then applying the operation of the optimal connection of cycles into one Hamiltonian cycle. The computational complexity of the algorithm does not exceed $O$(|$V$|$^{3}$). We present a proof of the theorem that for the metric traveling salesman problem, the maximum accuracy of the algorithm is at least 5/6. The quality of the algorithm has been tested on randomly generated cost matrices with the Euclidean metric. An analytical and numerical study of the algorithm for combining cycles has allowed us to move the hypothesis about the asymptotic accuracy of the algorithm on the class of metric traveling salesman problems to the maximum.

Détail

Keywords: algorithm, asymptotic accuracy, computational complexity, computational experiment, traveling salesman problem.