12
$\begingroup$

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 over a year ago, with no answers.

Improve this question
$\endgroup$
9
  • $\begingroup$ Duplicate of math.stackexchange.com/questions/935677/… (no answer given though). $\endgroup$
    – Tony Huynh
    Commented Nov 4, 2015 at 21:42
  • $\begingroup$ @TonyHuynh Yes I asked this on MSE over a year ago and received no response so thought I should take it here. $\endgroup$
    – user82330
    Commented Nov 5, 2015 at 15:52
  • 3
    $\begingroup$ No problem; it's a nice question. However, it is good etiquette to post a link to the other question in the post (on both sites). This prevents somebody working on the problem when it has already been solved elsewhere, for example. $\endgroup$
    – Tony Huynh
    Commented Nov 5, 2015 at 16:04
  • 1
    $\begingroup$ A while ago, somebody showed me the variant of this where the salesman doesn't return to the initial vertex at the end. In that case the answer was that FN was never better than NN, and the idea of the proof was to show by induction on $n$ that the $n$th shortest step in NN must be at most as long as the $n$th shortest step in FN, but I'd have to think hard to fill in the details. As I can't remember the whole argument, I don't know if it also works for the "cycle" version. Though presumably there was some reason he specified the "don't return" version. $\endgroup$
    – Jeremy Rickard
    Commented Nov 6, 2015 at 14:29
  • 1
    $\begingroup$ By the way, in the asymmetric version it's easy to make FN better than NN even with three vertices: make $A\to B$ slightly shorter than $A\to C$, but $C\to A$ absolutely enormous compared to all other lengths. $\endgroup$
    – Jeremy Rickard
    Commented Nov 6, 2015 at 14:44

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.