Применение дополнений паросочетаниями для решения задачи MAX TSP

Изложен подход к приближенному решению задачи коммивояжера на максимум (MAX TSP), основанный на дополнении частичного тура просочетаниями подграфа открытых вершин. Проведено аналитическое исследование, показавшее, что алгоритм, основанный на непосредственном применении данного подхода, во-первых, имеет вычислительную сложность не более $O(n^3)$, $n$ - число городов, во-вторых, не улучшает гарантированные оценки точности известных алгоритмов. Предложена модификация алгоритма Сердюкова, имеющая оценку вычислительной сложности $O(n^3)$ и наилучшую гарантированную оценку точности. Представлены результаты вычислительного эксперимента, позволяющие выдвинуть гипотезу об асимптотической точности алгоритма для достаточно широкого класса задач.

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

гамильтонов цикл, задача коммивояжера, приближенный алгоритм, паросочетание, оценки точности, вычислительная сложность, вычислительный эксперимент

Литература

1. Гимади, Э.Х. О некоторых результатах для задачи коммивояжера на максимум / Э.Х. Гимади, А.И. Cердюков // Дискретный анализ и исследование операций. - 2001. - № 1. - С. 22 - 39.
2. Панюков, А.В. Исследование реализаций алгоритма Сердюкова для задачи MAX TSP /А.В. Панюков, С.А. Тычинин // Российская конференция 'Дискретная оптимизация и исследование операций': материалы конф. (Владивосток, 7 - 14 сентября 2007). - Новосибирск, 2007. - С. 132.
3. Тычинин, С.А. Алгоритм дополнения подграфами для решения задачи MAX TSP /С.А. Тычинин // Информационный бюллетень ассоциации математического программирования № 11: Конференция 'Математическое программирование и приложения (тезисы докладов)'. - Екатеринбург, 2007. - С. 217 - 218.
4. 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.
5. Chen, Zh. Improved Deterministic Approximation Algo-rithms for Max TSP / Zh. Chen, Y. Okamoto, L. Wang // Inform. Process. Lett. - 2005. - № 95. - P. 333 - 342.
6. Gabow, H. An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs / H. Gabow // J. of the ACM. - 1976. - № 4. - P. 221 - 234.
7. Hartvigsen, D. Extensions of matching theory: PhD Thesis / D. Hartvigsen - Pittsburg, PA: Carnegie Mellon Univ, 1984. - 148 p.
8. Hassin, R.A 7/8 -approximation algorithm for metric Max TSP / R. Hassin, S. Rubinstein // Inform. Process. Lett. - 2002. - № 81. - P. 247 - 251.
9. Hassin, R. Better approximations for Max TSP / R. Hassin, S. Rubinstein // Inform. Process. Lett. - 2000. - № 75. - P. 181 - 186.