An Empirical Study of the Quality of the Cycle Merging Algorithm for the Maximum Traveling Salesman Problem

The maximum traveling salesman problem (MAX TSP) is a mathematical optimization problem that requires the construction of a Hamiltonian cycle with the highest possible sum of edge weights. It finds applications in bioinformatics, coding, logistics, and numerous other fields. Despite the existence of theoretical bounds on the accuracy of approximation algorithms, their practical behavior remains insufficiently explored. In this study, we conduct an empirical analysis of the Cycle Merging Algorithm (CMA) for solving MAX TSP. The CMA is a greedy heuristic based on the sequential merging of cycles in a maximum-weight 2-factor. Our computational experiments, carried out on instances ranging from 100 to 3000 vertices, evaluate the accuracy of the CMA solutions relative to an upper bound determined by solving an assignment problem, as well as the algorithm's computational efficiency. A significant contribution of this work is the construction of a regression model that describes the dependency of the relative error estimate on the number of vertices for metric instances. The model demonstrates that the relative error decreases according to a power-law relationship, and the analysis confirms that the CMA consistently outperforms its guaranteed theoretical bound. The results indicate that the Cycle Merging Algorithm is a powerful heuristic for MAX TSP, providing high-quality solutions and computational efficiency in practice. Future research directions include optimizing the cycle merging strategy, developing hybrid algorithms, and implementing GPU-based version to enhance scalability.