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.

Keywords

maximum traveling salesman problem; approximation algorithms; computational experiment; regression analysis; algorithmic complexity.

References

1. Reingold E.M., Nievergelt J., Deo N. Combinatorial Algorithms: Theory and Practice. New Jersey, Prentice-Hall, 1977. DOI: 10.2307/2987917
2. Sichen Zhong, Zhao Lu, Liang Yiang, Zamani M., Patro R., Chowdhury R.,Arkin E.M., S.B. Mitchell J., Skiena S. Optimizing Read Reversals for Sequence Compression. International Workshop on Algorithms in Bioinformatics, Atlanta, September 10-12, 2015. Springer, Berlin, Heidelberg, 2015, pp. 189-202. DOI: 10.1007/978-3-662-48221-6_14
3. Leonova Y.F., Panyukov A.V. Application of the Cycles Merging Algorithm to the Shortest Common Superstring Problem. 2020 Global Smart Industry Conference (GloSIC), IEEE, 2020, pp. 342-347. DOI:10.1109/glosic50886.2020.9267863
4. Gimadi E.K., Glebov N.I., Serdyukov A.I. On Finding a Cyclic Tour and a Vehicle Loading Plan Yielding Maximum Profit. Discrete Applied Mathematics, 2004, vol. 135, no. 1-3, pp. 105-111. DOI:10.1016/s0166-218x(02)00298-6
5. Kaplan H., Lewenstein M., Shafrir N., Sviridenko M. Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs. Journal of the ACM (JACM), 2005, vol. 52, no. 4, pp. 602-626. DOI:10.1145/1082036.1082041
6. Paluch K., Mucha M., Madry A. A 7/9-approximation Algorithm for the Maximum Traveling Salesman Problem. International Workshop on Approximation Algorithms for Combinatorial Optimization, Berlin, Heidelberg, Springer Berlin Heidelberg, 2009, pp. 298-311. DOI:10.1007/978-3-642-03685-9_23
7. Kowalik L., Mucha M. 35/44-approximation for Asymmetric Maximum TSP with Triangle Inequality. Algorithmica, 2011, vol. 59, pp. 240-255. DOI:10.1007/s00453-009-9306-3
8. Kowalik L., Mucha M. Deterministic 7/8-approximation for the Metric Maximum TSP. Theoretical Computer Science, 2009, vol. 410, no. 47-49, pp. 5000-5009. DOI:10.1016/j.tcs.2009.07.051
9. Glover F., Gutin G., Zverovich A., Yeo A. Construction Heuristics for the Asymmetric TSP. European Journal of Operational Research, 2001, vol. 129, no. 3, pp. 555-568. DOI:10.1016/s0377-2217(99)00468-3
10. Shenmaier V. Asymptotic Optimality of the Greedy Patching Heuristic for Max TSP in Doubling Metrics. Data Structures and Algorithms, 2022. DOI:10.48550/arXiv.2201.03813
11. Leonova Y.F., Panyukov A.V. [Cycle Merging Algorithm for Approximate Solution of the Travelling Salesman Problem]. Tezisy XIX Vserossijskoj konferencii molodyh uchjonyh po matematicheskomu modelirovaniju i informacionnym tehnologijam, Novosibirsk, 2018, pp. 28-29. (in Russian)