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

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?

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