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?
The two paragraphs talk about different variants of the TSP. In both cases, the length of the edges are not required to satisfy the triangle inequality. However,...
The first variant allows a circuit to go through a node multiple times. Replacing the length of an edge with the length of the shortest path gives shortest tours the same length as the shortest circuits of the original graph, and guarantees that the triangle inequality holds.
The second variant is the standard non-metric TSP. The reduction to metric TSP changes, in this case, the tour length. The bound on the ratio of the tour length found by an algorithm to the optimal length applies to the transformed graph, not to the original graph.