Cycles Merging Algorithm for Metric Maximum Traveling Salesman Problem
DOI:
https://doi.org/10.14529/cmse210402Keywords:
algorithm, asymptotic accuracy, computational complexity, computational experiment, traveling salesman problemAbstract
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 was tested on randomly generated cost matrices with the Euclidean metric. An analytical and numerical study of the algorithm for combining cycles allowed us to move the hypothesis about the asymptotic accuracy of the algorithm on the class of metric traveling salesman problems to the maximum.
References
Tong W., Goebel R., Liu T., Lin G. Approximation algorithms for the maximum multiple RNA interaction problem. International Conference on Combinatorial Optimization and Applications, Chengdu, China, December 12–14, 2013. Springer, Cham, 2013. P. 49–59. DOI: 10.1007/978-3-319-03780-6_5.
Sichen Z., Zhao L., Liang Y. et al. Optimizing read reversals for sequence compression. International Workshop on Algorithms in Bioinformatics, Atlanta, GA, USA, September 10–12, 2015. Springer, Berlin, Heidelberg, 2015. P. 189–202. DOI: 10.1007/978-3-662-48221-6_14.
Hassin R., Rubinstein S. An approximation algorithm for maximum triangle packing. Discrete applied mathematics. 2006. Vol. 154, no. 6. P. 971–979. DOI: 10.1016/j.dam.2005.11.003.
Chen Z.Z., Wang L. An improved approximation algorithm for the bandpass-2 problem. International Conference on Combinatorial Optimization and Applications, Banff, AB, Canada, August 5–9, 2012. Springer, Berlin, Heidelberg, 2012. P. 188–199. DOI: 10.1007/978-3-642-31770-5_17.
Harari F. Graph Theory. Chapter 9. Factorization. Moscow: Editorial URSS, 2003. 296 p. (in Russian)
Barvinok A.I., Johnson D.S., Woeginger G.J., Woodroofe R. Finding maximum length tours under polyhedral norms. Proceedings of IPCO VI, Lecture Notes in Computer Science, Houston, Texas, June 22–24, 1998. 1998. Vol. 1412. P. 195–201. DOI: 10.1007/3-540-69346-7_15.
Fisher M.L., Nemhauser G.L., Wolsey L.A. An analysis of approximations for finding a maximum weight Hamiltonian circuit. Operations Research. 1979. Vol. 27, no. 4. P. 799–809. DOI: 10.1287/opre.27.4.799.
Kosaraju S.R., Park J.K., Stein C. Long tours and short superstrings. Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, November 20–22, 1994. IEEE, 1994. P. 166–177. DOI: 10.1109/sfcs.1994.365696.
Hassin R., Rubinstein S. An approximation algorithm for the maximum traveling salesman problem. Information Processing Letters. 1998. Vol. 67, no. 3. P. 125–130. DOI: 10.1016/s0020-0190(98)00102-1.
Serdyukov A.I. An algorithm with an estimate for the traveling salesman problem for a maximum. Discrete analysis and operations research. 1984. No. 25. P. 80–86. (in Russian)
Panyukov A.V., Tychinin S.A. The use of matching additions for solving MAX TSP. Bulletin of South Ural State University. Series: Mathematical modeling and programming. 2008. No. 15(115). P. 54–63. (in Russian)
Hassin R., Rubinstein S. Better approximations for MAX TSP. Information Processing Letters. 2000. Vol. 75, no. 4. P. 181–186. DOI: 10.1016/s0020-0190(00)00097-1.
Chen Z.Z., Okamoto Y., Wang L. Improved deterministic approximation algorithms for MAX TSP. Information Processing Letters. 2005. Vol. 95, no. 2. P. 333–342. DOI: 10.1016/j.ipl.2005.03.011.
Paluch K., Mucha M., Madry A. A 7/9-approximation algorithm for the maximum traveling salesman problem. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Berkeley, CA, USA, August 21–23, 2009. Springer, Berlin, Heidelberg, 2009. P. 298–311. DOI: 10.1007/978-3-642-03685-9_23.
Dudycz S., Marcinkowski J., Paluch K., Rybicki B. A 4/5-approximation algorithm for the maximum traveling salesman problem. International Conference on Integer Programming and Combinatorial Optimization, Waterloo, ON, Canada, June 26–28, 2017. Springer, Cham, 2017. P. 173–185. DOI: 10.1007/978-3-319-59250-3_15.
Kostochka A.V., Serdyukov A.I. Polynomial algorithms with the estimates 3/4 and 5/6 for the Traveling Salesman Problem of the maximum. Managed systems. 1985. No. 26. P. 55–59. (in Russian)
Hassin R., Rubinstein S. A 7/8-approximation algorithm for metric MAX TSP. Information processing letters. 2002. Vol. 81, no. 5. P. 247–251. DOI: 10.1016/s0020-0190(01)00234-4.
Glover F., Gutin G., Yeo A., Zverovich A. Construction heuristics for the asymmetric TSP. European Journal of Operational Research. 2001. Vol. 129, no. 3. P. 555–568. DOI: 10.1016/s0377-2217(99)00468-3.
Goldengorin B., Jäger G., Molitor P. Tolerance based contract-or-patch heuristic for the asymmetric TSP. Workshop on Combinatorial and Algorithmic Aspects of Networking, Chester, UK, July 2, 2006. Springer, Berlin, Heidelberg, 2006. P. 86–97. DOI: 10.1007/11922377_8.
Kuzyurin N.N., Fomin S.A. Efficient algorithms and computational complexity: a tutorial. Moscow: MIPT, 2007. 311 p. (in Russian)
