HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
asymmetricsymmetrictspconcerningapproximationmetricand

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#130171, answer score: 4

Revisions (0)

No revisions yet.