# Nearest neighbor algorithm for TSP when triangle inequality holds

The output given by this nearest neighbor algorithm for the Travelling Salesman Problem can be arbitrarily bad. In the example constructed here, the triangle inequality doesn't hold in most cases.

Let $$L$$ be the set of positive real numbers $$r\in\mathbb{R}_+$$ such that for every setting of TSP such that the triangle equality holds, we have that the length of the tour that the nearest neighbor algorithm gives is at most $$r\cdot \ell$$, where $$\ell$$ is the optimal (minimal) length of any tour.

Question. Is $$L$$ non-empty? If yes, what is $$\inf L$$?

## 1 Answer

The set $$L$$ is empty.

Theorem 2 in this paper shows that, for any integer $$m > 3$$, there exists an instance with $$n = 2^m - 1$$ cities such that it satisfies the triangle inequality and the approximation ratio of the nearest neighbor algorithm on this instance is larger than $$\frac{\log(n+1)}{3}$$.

Pick your favorite $$x \in \mathbb{R}_+$$, and choose $$m= 4\lceil x \rceil$$. By the above theorem, the approximation ratio must be larger than $$\frac{\log(n+1)}{3} = \frac{\log 2^m}{3} = \frac{m}{3} > x$$. This shows that $$x \not\in L$$.

(All logarithms are in base 2)