2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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"? $\endgroup$ – Discrete lizard Sep 15 '20 at 8:59
  • $\begingroup$ @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. $\endgroup$ – J. Schmidt Sep 15 '20 at 9:43
3
$\begingroup$

Here is an excerpt from the introduction to an earlier paper of Svensson, Tarnawski and Végh, which was the first to give a constant factor approximation algorithm for ATSP:

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.

$\endgroup$
6
  • $\begingroup$ For completeness : ATSP is thus inapproximable in general, while Metric ATSP is approximable, and whenever one talks about approximating ATSP, one actually means Metric ATSP. $\endgroup$ – J. Schmidt Sep 15 '20 at 9:46
  • $\begingroup$ @J.Schmidt Not exactly. Metric implies that we have both the triangle inequality and symmetry. For ATSP, only the triangle inequality is assumed. I think this means that for example Christofides algorithm doesn't work for approximating ATSP. That would explain why these researchers consider a 500 or so factor of approximation for this problem an interesting result. $\endgroup$ – Discrete lizard Sep 15 '20 at 11:02
  • $\begingroup$ @Discretelizard I'm pretty confident this is not the case. Symmetric TSP implies symmetry, Asymmetric TSP implies asymmetry, and Metric TSP implies triangle inequality. Metric TSP can be considered in the context of either symmetry or asymmetry. (I have of course been wrong before.) $\endgroup$ – J. Schmidt Sep 15 '20 at 12:20
  • $\begingroup$ @J.Schmidt Huh, well that is a rather weird name then, considering what metric usually means. But well, certainly not the most gratuitous use of the word "metric". More to the point, what are your thoughts about whether Christofides algorithm can be solved used for "metric" ATSP? If it can, I don't quite understand what it is these people are doing in this paper. $\endgroup$ – Discrete lizard Sep 15 '20 at 12:29
  • 1
    $\begingroup$ @Discretelizard in fact, after going through Wikipedia's definition of "metric", it does seem to imply symmetry as well as the triangle inequality, and not only the triangle inequality as I first thought ! I suppose a complete answer to my original post would thus be : Asymmetric TSP in general is inapproximable, however Asymmetric TSP respecting the triangle inequality is approximable. $\endgroup$ – J. Schmidt Sep 15 '20 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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