Approximate algorithms for the traveling salesperson problem

Abstract

Several polynomial time algorithms finding "good," but not necessarily optimal, tours for the traveling salesman problem are considered. For the nearest neighbor method, the worst case ratio of the obtained tour to the optimal tour is shown to increase logarithmically with the number of cities. For another method, which we call the nearest insertion method, the worst case ratio is shown to approach 2 as the number of cities increases. It is also shown that for any n ≥ 8, there are traveling salesman problems with n cities having tours which are k-optimal for all k ≤ n/4, and for which the ratio with respect to the optimal is 2(1 -1/n).