When does the nearest neighbor heuristic fail for the Traveling Salesperson?

Problem Detail: 

Can you provide an example of NN algorithm failure on the Euclidean traveling salesman problem?

I was trying to construct a specific example of this for my friends and was failing.

Asked By : dylan

Answered By : Karolis Juodelė

Consider a ladder

a----b----c |    |    | d----e----f 

Say length of a-b is $2$ and length of a-d is $1$. The optimal route is a-b-c-f-e-d-a, $10$ units long. Starting at a, NN would produce a-d-e-b-c-f-a which is $7 + \sqrt{17} > 11$ units long.

There is actually a four node example, a rhombus

  A  /|\ B-+-C  \|/   D 

Say length of B-C is $10$, length of A-D is $24$ and thus length of A-B is $13$. The optimal route is A-B-D-C-A, $52$ units long. NN would produce the path A-B-C-D-A, $60$ units long.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13742