An approximation algorithm for the maximum traveling salesman problem

Задача коммивояжера состоит в следующем: учитывая список городов и расстояние между каждой парой городов, необходимо составить самый короткий маршрут, по которому каждый город посещается ровно один раз и маршрут заканчивается в том городе, к котором начинался. Это NP-сложная проблема в комбинаторной оптимизации, важной в исследовании операций и теоретической информатике. Задача коммивояжера – одна из самых известных и исследуемых проблем в информатике. В статье описывается приближенный алгоритм решения задачи коммивояжера на максимум, основанный на двух известных полиномиальных алгоритмах. Точность данного алгоритма составляет 25/33.