Анализ градиентного решения задачи коммивояжера

Приводится вариант градиентного алгоритма трудоемкостью $O(n^3)$, гарантирующий получение маршрута в задаче коммивояжера, длина которого не меньше половины длины максимального маршрута в случае симметричной матрицы расстояний и не меньше трети – в случае несимметричной.