0
$\begingroup$

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$?

$\endgroup$

1 Answer 1

1
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.