Polynomial time approximation methods for TSP

Question

I am aware that the Christofides algorithm is the best known polynomial-time algorithm for approximating solutions to the traveling salesman problem, but it only works for the metric TSP. Does anyone know the best polynomial-time approximation algorithm for the non-metric (but still symmetric) TSP? What about asymmetric TSP? Despite a lot of searching with Google, I have been unable to find this information online.

Answer 1

There is no known polynomial-time approximation algorithm for the non-metric TSP, even in the symmetric case. The existence of such an algorithm would imply P = NP, so there is good evidence that no such algorithm exists. This is because a non-metric TSP approximation algorithm would give a solution to the Hamiltonian cycle problem.

Suppose there was a function $f:\mathbb N\to \mathbb N$, and polynomial-time algorithm which, given a complete weighted graph with $n$ vertices, outputs an $n$-vertex cycle whose weight is at most $f(n)$ times the optimal length cycle. Let $G$ be an arbitrary (unweighted) graph with $n$ vertices; we want to determine if $G$ has a Hamiltonian cycle. Define a complete weighted graph, $G^*$, as follows. $$ \text{weight}(u,v)=\begin{cases} 1 & \text{if $u$ is joined to $v$ in $G$} \\ n\times f(n) & \text{if $u\neq v$, and $u$ is not joined to $v$ in $G$} \end{cases} $$ Note that if $G$ has a Hamiltonian cycle, then the optimal TSP cycle of $G^*$ has a weight of $n$, while if $G$ does not have a Hamiltonian cycle, then the weight of the optimal TSP cycle for $G^*$ is more than $n\cdot f(n)$. You can then use the purported approximation algorithm on $G^*$; if the outputted path has weight $n$, then $G$ has a Hamiltonian cycle, and if the optimal path has weight more than $n\times f(n)$, then $G$ does not have a Hamiltonian cycle.