MATCHING SUPPLEMENT APPLICATION FOR SOLVING MAX TSP
Keywords:
Hamilton cycle, travelling salesman problem, approximation algorithm, approximation ratio, matching, time complexity, computational experimentAbstract
An approach to approximation solving of MAX TSP based on supplementation of partial tours by matchings of the open vertexes subgraphs is presented in the paper. Analytical research demonstrates that this algorithm firstly have time complexity no more than $O(n^3)$, here $n$ is the number of towns, and secondly does not improve the guaranteed accuracy ratio of the known algorithms. The modification of Serdukov algorithm with time complexity $O(n^3)$ and best known guaranteed accuracy ratio is presented. Computational experiment results cause to anticipate asymptotic accuracy of this algorithm for a broad spectrum of MAX TSP.References
Гимади, Э.Х. О некоторых результатах для задачи коммивояжера на максимум / Э.Х. Гимади, А.И. Cердюков // Дискретный анализ и исследование операций. - 2001. - № 1. - С. 22 - 39.
Панюков, А.В. Исследование реализаций алгоритма Сердюкова для задачи MAX TSP /А.В. Панюков, С.А. Тычинин // Российская конференция 'Дискретная оптимизация и исследование операций': материалы конф. (Владивосток, 7 - 14 сентября 2007). - Новосибирск, 2007. - С. 132.
Тычинин, С.А. Алгоритм дополнения подграфами для решения задачи MAX TSP /С.А. Тычинин // Информационный бюллетень ассоциации математического программирования № 11: Конференция 'Математическое программирование и приложения (тезисы докладов)'. - Екатеринбург, 2007. - С. 217 - 218.
The maximum traveling salesman problem under polyhedral norms /A.I. Barvinok, D.S. Johnson, G. Woeginger, R. Woodroofe // Integer Programming and Combinatorial Optimization. - Berlin, 1999. - P. 195 - 201.
Chen, Zh. Improved Deterministic Approximation Algo-rithms for Max TSP / Zh. Chen, Y. Okamoto, L. Wang // Inform. Process. Lett. - 2005. - № 95. - P. 333 - 342.
Gabow, H. An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs / H. Gabow // J. of the ACM. - 1976. - № 4. - P. 221 - 234.
Hartvigsen, D. Extensions of matching theory: PhD Thesis / D. Hartvigsen - Pittsburg, PA: Carnegie Mellon Univ, 1984. - 148 p.
Hassin, R.A 7/8 -approximation algorithm for metric Max TSP / R. Hassin, S. Rubinstein // Inform. Process. Lett. - 2002. - № 81. - P. 247 - 251.
Hassin, R. Better approximations for Max TSP / R. Hassin, S. Rubinstein // Inform. Process. Lett. - 2000. - № 75. - P. 181 - 186.
