Improved Approximation Algorithm for TSP
Sheng-Da CHEN · Computer Engineering and Applications Journal · 2006
Traveling Salesman Problem(TSP) is a typical combinatorial optimization problem.It has been proved that TSP is of NPC complexity.This paper improves the position of inserted point based on 2-approximation algorithm closest-point for solving TSP,and proposes an efficient approximation algorithm CPBOA.Some typical instances in TSPLIB are used to test this algorithm,which are compared with MST-PRIM and closest-point.The computational results show that this algorithm can get better solution,and the time spending is less than closest-point.