An approximation algorithm for the TSP

The authors present a new polynomial-time heuristic algorithm for finding a solution to the Travelling Salesman Problem (TSP) for any complete and edge-weighted graph Kn, with a set of vertices V and a set of edges E where ℝVℝ=n. In a few words, this method is based on the idea of linking the elements of V progressively, one by one, in such a way that the vertex selection which produces fewest disturbances to the other vertices not yet connected, will be selected as the next vertex to join to the subset of already connected vertices. When the cost of the result is compared to the cost of the best circuit, it appears that a good sub-solution is obtained in most of the cases tested. Moreover, comparison tests made between the heuristic introduced and the well-known Quick method, produce a better behaviour, for almost every case, in the first approach.