Approximation bounds on the Nearest Neighbour Algorithm for the TSP.
-1
$begingroup$
I am currently studying about the Nearest Neighbour Algorithm applied to the TSP, and I want to check if there are any performance bounds on it. I have came across the following paper on the logarithmic bound for euclidean TSP. I came across this paper : Rosenkrantz, Daniel & Edwin Stearns, Richard & M. Lewis II, Philip. (1977). An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM J. Comput.. 6. 563-581. 10.1137/0206041. I however am I bit confused because, in page 564 it says that this can also apply to the classical tsp problem. However, in the paragraph after it, it says that it does not. Can anyone help clarify this?
computer-science
share | cite | im