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

Аннотация

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