-1

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?

Dylan Galea
  • 15
  • I assume you are referring to the K-Nearest Neighbours method of classifying a categorical variable? Can you explain what TSP is please? – DanielOnMSE Dec 06 '18 at 15:04
  • @DanielOnMse TSP is the Travelling Salesman Problem. The problem of finding a minimum weight Hamiltonian cycle in a complete undirected positively weighted graph. The Nearest Neighbour Algorithm is the algorithm that constructs a minimum weight Hamiltonian cycle by starting at an arbitrary vertex and always visiting the unvisited vertex closest to it. – Dylan Galea Dec 06 '18 at 15:12
  • well... I have nothing to contribute here ahahah I thought maybe this was a stats question... K-Nearest Neighbours is a thing in statistics. My bad! Of course now I read your tag it says Computer Science... silly me :P – DanielOnMSE Dec 06 '18 at 15:14

1 Answers1

0

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.

Fabio Somenzi
  • 7,676
  • @Somenzi , thanks this helped a lot. Do you happen to know of any bounds to the NN algorithm applied to the general TSP? – Dylan Galea Dec 07 '18 at 03:11
  • Quoting from Vazirani's Approximation Algorithms, "For any polynomial time computable function $\alpha(n)$, TSP cannot be approximated within a factor of $\alpha(n)$, unless P = NP." – Fabio Somenzi Dec 07 '18 at 04:39
  • @Somenzi, ah so we do not know if there is one, otherwise the P= NP open question would have been known – Dylan Galea Dec 07 '18 at 07:53
  • Yes, if we knew that P $\neq$ NP, we would know that there is no way to approximate TSP within a factor of $\alpha(n)$. If we knew that P = NP, we would know that there is a polynomial algorithm to solve TSP exactly. – Fabio Somenzi Dec 07 '18 at 07:59