This is a problem that has bugged me for quite some time, and I have not been able to find any documentation about it online. It is well known that the NN algorithm can yield the worst possible route - for small cases it would seem any (undirected) complete weighted graph with this property forces the FN algorithm to produce an equally bad route. 


Naturally this raises the question whether FN can ever produce a shorter path than NN - I am mostly interested in the symmetric TSP here.
Any input would be greatly appreciated.


Posted on [MSE](https://math.stackexchange.com/questions/935677/traveling-salesman-problem-can-a-terrible-strategy-beat-a-good-one) over a year ago, with no answers. 



Travelling salesman: can the furthest-neighbour algorithm beat the nearest-neighbour?
Label the vertices of the NN path by $0,1,2,\dots,n=0$. Let $x\_0=0,x\_1,\dots,x\_n=0$ be the FN path. Define $A=\{i\in \{1,\dots,n-1\}| \exists j>i \text{ with } x\_j>x\_i\}$. Then for any $i\in A$ we have by construction $d(x\_i,x\_i+1)\leq d(x\_i,x\_j)\leq d(x\_i,x\_{i+1})$. Let $b\_0=0< b\_1\dots < b\_k=n-1$ be the elements of $\{0\}\cup A^c=\{0,1,\dots,n-1\} \backslash A$. Again by construction we have $d(x\_{b\_{i+1}},x\_{b\_{i+1}}+1)\leq d(x\_{b\_{i+1}},x\_{b\_{i}})\leq d(x\_{b\_i},x\_{b\_i+1})$ for all $i\in \{0,\dots,k-1\}$. Furthermore we have $d(x\_{b\_0},x\_{b\_0}+1)=d(0,1)\leq d(n-1,0)=d(x\_{b\_k},x\_{b\_k+1})$. Summing up all inequalities yields that the length of the NN path is at most as long as the path of the FN path.


