A polynomial approximation algorithm for the traveling salesman problem
Jing Zhong Fang · Caai Transactions on Intelligent Systems · 2010
The traveling salesman problem (TSP)is a typical combinational optimization problem which is easy to describe and hard to solve. For large-scale TSP problems,an effective solution has yet to be found. To improve the time performance of the elastic net method in solving large scale TSPs,faster algorithms were investigated. Use of the elastic net method,the expansion method and the shrink method were proposed. The time complexities of these algorithms were less than O(N3). After comparison and analysis it was clear that the results of the expansion method were comparatively ideal. Based on analysis of the expansion method,a stochastic expansion method and a complete expansion method were developed. The time complexity of the complete expansion method was less than O(N4),and it was still a polynomial algorithm. Practical examples showed that the complete expansion method is fast and efficient.