Алгоритм соединения циклов для метрической задачи коммивояжера на максимум

Анатолий Васильевич Панюков, Юлия Федоровна Леонова

Аннотация


Задача коммивояжера на максимум имеет ряд практических приложений, например, при сжатии произвольных данных и анализе последовательностей ДНК. При том, что задача коммивояжера на максимум является менее разработанной, чем задача коммивояжера на минимум, для ее решения существуют эффективные приближенные алгоритмы. В статье приведены оценки точности лучших на сегодняшний день алгоритмов для приближенного решения метрической задачи коммивояжера на максимум, и предлагается еще один алгоритм приближенного решения задачи коммивояжера на максимум, состоящий из поиска 2-фактора максимального веса в заданном графе, а затем применения операции оптимального соединения циклов в один гамильтонов цикл. Приведено доказательство, что для метрической задачи коммивояжера на максимум отношение длины найденного алгоритмом гамильтонова цикла к максимально возможной длине гамильтонова цикла не менее 5/6. Вычислительная сложность алгоритма не превышает O(|V|3). Проведено тестирование качества алгоритма на случайно сгенерированных матрицах стоимостей с евклидовой метрикой. Аналитическое и численное исследование алгоритма объединения циклов позволило выдвинуть гипотезу об асимптотической точности алгоритма на классе метрических задач коммивояжера на максимум.


Ключевые слова


алгоритм; асимптотическая точность; вычислительная сложность; задача коммивояжера

Полный текст:

PDF

Литература


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)




DOI: http://dx.doi.org/10.14529/cmse210402