0
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ +1 --> Thanks for your intuitive example and the link to the paper! $\endgroup$ Jul 19, 2021 at 16:29

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.