# Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP

I always considered Symmetric TSP to be inapproximable in general, and thus by extension Asymmetric TSP as well. Once you add the condition of the triangle inequality however, you obtain Metric TSP (which can be Symmetric or Asymmetric), which is approximable (e.g. Christofides algorithm).

However, I'm having doubts after finding the following paper :

An improved approximation algorithm for ATSP
Vera Traub, Jens Vygen (https://arxiv.org/pdf/1912.00670.pdf)

In their paper, there is no mention of Metric TSP, or the triangle inequality. Does this mean that I'm misunderstanding, i.e. Asymmetric TSP is in fact approximable, even without the triangle inequality?

EDIT : As Discrete Lizard pointed out, Metric TSP seems to not just imply (any) TSP respecting the triangle inequality, but rather Symmetric TSP respecting the triangle inequality. This does not change my last question though, and Yuval Filmus' answer is still correct.

• Well, doesn't the paper clearly say there recently has been a constant factor approximation algorithm for ATSP? The question is of course whether you trust this pair of papers, but I don't see what sort of answer your looking for, really. Or are you asking what the merit is of an argument of the form "there is no triangle inequality, so we can't have an approximation"? – Discrete lizard Sep 15 '20 at 8:59
• @Discretelizard there's a simple proof showing ATSP in general in inapproximable. However, as Yuval's answer indicates, the problem is often "relaxed" and thus assumed Metric, which answers my question : ATSP is inapproximable in general, Metric ATSP is approximable. – J. Schmidt Sep 15 '20 at 9:43

Without any assumptions on the distances, a simple reduction from the problem of deciding whether a graph is Hamiltonian shows that it is NP-hard to approximate the shortest tour to within any factor. Therefore it is common to relax the problem by allowing the tour to visit cities more than once. This is equivalent to assuming that the distances satisfy the triangle inequality: the distance from city $$i$$ to $$k$$ is no larger than the distance from $$i$$ to $$j$$ plus the distance from $$j$$ to $$k$$. All results mentioned and proved in this paper refer to this setting.