Opposite-nearest neighbor algorithm vs. nearest neighbor algorithm Take the traveling salesman problem, but with three slight twists:

*

*You can choose a different start vertex for each of the two algorithms.

*Each path from one vertex to another is of unique, arbitrary length (irrespective of the distances between the cities and they don't intersect).

*Each algorithm goes to each vertex once and only once (it doesn't return to its starting vertex).
With these conditions, is it possible for a furthest neighbor algorithm to beat a nearest neighbor algorithm.

I've tried using induction, but condition 2. really throws it off.
 A: To answer your question, YES, if the length of an edge is the same in
each direction, then starting at a vertex $y_1$ and picking the next edge of maximum length
that visits a new vertex will return a Hamiltonian path that is at least
as long as the Hamiltonian path returned by starting at a vertex $u_1$ picking
the next edge of minimum length that
visits a new vertex, for any choices of the starting vertices $y_1$ and $u_1$ in the complete graph.
If the starting vertices are the same,
then picking the next edge of maximum length
that visits a new vertex will return a Hamiltonian path that is strictly
longer than the Hamiltonian path returned by picking
the next edge of minimum length that
visits a new vertex.
To elaborate: Let $K_N$ be a complete graph with a length
function $\ell$ on the edges of $K_N$ that satisfies the following:

*

*No two edges incident to the same vertex are of the
same length.


*$\ell(vw)=\ell(wv)$ for every pair of vertices $w,v \in K_N$.
Let $u_1$ be a vertex in $K_N$ and let
$P^{\min}(u_1)$ be the Hamiltonian path $u_1u_2\ldots u_N$ on the
complete graph $K_N$ chosen
as follows: For each $j$, the edge $u_ju_{j+1}$ is
the edge with the smallest length incident to $u_j$ and not in
$\{u_ju_1, \ldots, u_ju_{j-1}\}$. Let $y_1$ be a vertex in $K_N$ and let
$P^{\max}(y_1)$ be the Hamiltonian
path $y_1y_2 \ldots y_N$ on the complete graph chosen as follows:
For each $k$, the edge $y_ky_{k+1}$ is the edge with the biggest
length incident to $y_k$ and not in $\{y_ky_1, \ldots, y_ky_{k-1}\}$.

THM 1: Then there is a complete matching $M$ that matches each edge
$u_ju_{j+1} \in P^{\min}(u_1)$ with an edge $M(u_ju_{j+1}) \doteq$
$y_ky_{k+1} \in P^{\max}(y_1)$ that satisfies the following:
$\ell(u_ju_{j+1}) \le \ell(M(u_ju_{j+1})) = \ell(y_ky_{k+1})$. In particular, the inequality $\ell(P^{\min}(u_1)) \le \ell(P^{\max}(y_1))$
for any 2 vertices $u_1,y_1 \in K_N$, where, in a slight overload of notation, $\ell(W) \doteq \sum_{i=1}^{r} \ell(v_iv_{i+1})$
for any walk $W=v_1v_2 \ldots v_rv_{r+1}$ in $K_N$.

First, for each integer $j$ let $\pi(j)$ be the integer $k$ such that
the $k$-th vertex $y_k$ of $P^{\max}(y_1)$ is the $j$-th vertex $u_j$
of $P^{\min}(u_1)$.
We construct $M$ for THM 1 as follows: We first find
$M(u_{N-1}u_{N})$, and then $M(u_{N-2}u_{N-1})$, and so on.
So let us assume that we have found $M(u_{N-j'}u_{N-j'+1})$ for
each positive integer $j'<j$. We now find $M(u_{N-j}u_{N-j+1})$
Case 1: If there exists a nonnegative integer $j' < j$ such that $\pi(N-j') > \pi(N-j)$,
put $M(u_{N-j}u_{N-j+1})$ to be the edge $y_{\pi(N-j)}y_{\pi(N-j)+1}$.
We claim the following:
$$M(u_{N-j}u_{N-j+1}) \doteq  
\ell(y_{\pi(N-j)}y_{\pi(N-j)+1}) \ge \ell(u_{N-j}u_{N-j+1}).$$
[Indeed, let us write $N-j'\doteq a$ where $j'$ is as above, and
let us write $N-j \doteq b$. Then both $a>b$ and $\pi(a)>\pi(b)$.
Then $\pi(b)<\pi(a)$ and the construction of $P^{\max}(y_1)$ gives
$\ell(y_{\pi(b)}y_{\pi(b)+1}) \ge \ell(y_{\pi(b)}y_{\pi(a)})$
Also, $b<a$ and the construction of $P^{\min}(u_1)$ gives
$\ell(u_bu_{b+1}) \le \ell(u_bu_a)$.
But $y_{\pi(b)}=u_b$ and $y_{\pi(a)}=u_a$ so
$\ell(u_au_b)$ $=$ $\ell(y_{\pi(a)}y_{\pi(b)})$.
So putting this together gives $$\ell(y_{\pi(b)}y_{\pi(b)+1}) 
\ge \ell(y_{\pi(b)}y_{\pi(a)}) = \ell(u_au_b)    
\ge \ell(u_bu_{b+1})$$
Note however that $\ell(u_bu_{b+1})=\ell(u_{N-j}u_{N-j+1})$
[because $N-j=b$] while $\ell(y_{\pi(b)}y_{\pi(b)+1})= 
M(u_{N-j}u_{N-j+1})$ and so this gives indeed
$\ell(y_{\pi(N-j)}y_{\pi(N-j+1)})$ $\ge \ell(u_{N-j}u_{N-j+1})$,
which is as desired.]
Case 2: If there does not exist a $j'$ as in Case 1.
Then the inequality $\pi(N-j) > \pi(N-j')$ for all integers
$j' < j$, so let us now set $j''$ to be the integer in
$\{0,1, \ldots , j-1\}$ so that $\pi(N-j'')$ is the
largest out of $\pi(N),\pi(N-1), \ldots \pi(N-j-1)\}$.
Then $\pi(N-j'')$ is the second largest out of
$\pi(N),\pi(N-1), \ldots \pi(N-j)$. So set
$M(u_{N-j}u_{N-j+1})$ to be the edge
$y_{\pi(N-j'')}y_{\pi(N-j'')+1}$. We claim the following:
$$M(u_{N-j}u_{N-j+1}) \doteq 
\ell(y_{\pi(N-j'')}y_{\pi(N-j'')+1}) \ge \ell(u_{N-j}u_{N-j+1}).$$
[Indeed, let us write $N-j'' \doteq a$ and $N-j \doteq b$. Then $a>b$
while $\pi(a) < \pi(b)$.
Then $\pi(a) < \pi(b)$ and
the construction of $P^{\max}(y_1)$ implies
$\ell(y_{\pi(a)}y_{\pi(a)+1}) \ge \ell(y_{\pi(a)}y_{\pi(b)})$ in $K_N$.
Also $b<a$ and the construction of $P^{\min}(u_1)$
implies $\ell(u_bu_{b+1})$ $\le$ $\ell(u_bu_a)$. However,
$u_a=y_{\pi(a)}$ and $u_b=y_{\pi(b)}$ so
$\ell(u_au_b)$ $=$ $\ell(y_{\pi(a)}y_{\pi(b)})$. So putting this
together gives
$$\ell(y_{\pi(a)}y_{\pi(a)+1}) \ge \ell(y_{\pi(a)}y_{\pi(b)}) = \ell(u_au_b)  
\ge \ell(u_bu_{b+1})$$
Note however that $\ell(u_bu_{b+1})=\ell(u_{N-j}u_{N-j+1})$
[because $N-j=b$] while $\ell(y_{\pi(a)}y_{\pi(a)+1})=
M(u_{N-j}u_{N-j+1})$ [because $N-j''=a$] and so this gives indeed
$\ell(y_{\pi(N-j'')}y_{\pi(N-j'')+1})$ $\ge \ell(u_{N-j}u_{N-j+1})$,
which is as desired.]
We can check that $M$ as defined above is indeed a matching as well, and
so THM 1 follows.
From this we conclude that the inequality $\ell(P^{\min}(u_1)) \le \ell(P^{\max}(y_1))$ holds
for all $u_1,y_1 \in V(K_N)$. $\surd$
We note that THM 1 holds if even if Condition 1. above for the length function $\ell$ does not hold.

We note that we cannot necessarily make the inequality in THM 1 strict.
To elborate, there are instances where $\ell(P^{\min}(u_1))=\ell(P^{\max}(y_1))$
for some $u_1,y_1 \in K_N$ even with Condition 1. above for the length function $\ell$ holding. Indeed, take $N=3$ and the graph $K_3$ on $\{y,w,v\}$ where $\ell(yw)=100$; $\ell(yv)=99$ and $\ell(wv)=1$. Then
$\ell(P^{\max}(y))= \ell(ywv) = \ell(P^{\min}(v))=\ell(vwy)$.
However if $u_1=y_1=v$ then [and condition 1. for $\ell$ holds] then the strict inequality $\ell(P^{\min}(v))< \ell(P^{\max}(v))$ holds
for all $N \ge 3$; to see this note that $M$ as constructed above
will map $u_1u_2=vu_2$
to $y_1y_2=vy_2$ and $\ell(u_1u_2) < \ell(y_1y_2)$.

We note that the condition that $\ell(wv)=\ell(vw)$ is a necessary
one for THM 1 to hold; otherwise take the graph $K_3$ on $\{y,w,v\}$ where
$\ell(yw)=100$; $\ell(wy)=1$; $\ell(yv)=\ell(vy)=1$ and
$\ell(wv)=\ell(vw)=2$. Then $P^{\min}(v) = vyw$ and has length $1+100=101$
whereas $P^{\max}(v)=vwy$ has length $2+1=3$.
