Can the "closest neighbor" algorithm get arbitrarily bad in TSP?

Question

Let's consider the following simple algorithm for attacking the Travelling Salesman Problem:

Choose the pair of cities $(A,B)$ where $A\neq B$ and the distance between $A, B$ is minimal amongst all the distances of the cities. Start with $A$, then visit $B$, then in each step visit the nearest city not visited already, until there is no more city left.

Given $k\in \mathbb{N}$, is there a setting of cities such that the total distance travelled is more than $k$ times the distance travelled in an optimal solution?

Answer 1

Consider an instance with $4$ cities $a, b, c, d$ and the following distances: $d(a,b)=1$, $d(a,c)=d(b,c)=2$, $d(a,d) = d(b,d) = 3$, $d(c,d) = M$ for some $M>3$.

Your algorithm visits the cities in one of the following two orders: $$ \langle a,b,c,d \rangle \quad \mbox{or} \quad \langle b,a, c, d\rangle. $$

In any case the cost of the tour is at least $d(c,d) = M$, while the tour $\langle a, d, b, c \rangle$ has cost at most $3 + 3 + 2 +2 = 10$. This shows that the solution returned by your algorithm can be at least $\frac{M}{10}$ times more costly than an optimal tour. Pick $M$ as large as you desire, e.g. $M=10k+1$.

Theorem 2 in this paper shows that the approximation ratio of the nearest neighbor algorithm can be $\Omega(\log n)$, where $n$ is the number of cities, even when distances satisfy the triangle inequality