Traveling Salesman Problem

is the problem of finding a Hamiltonian Cycle with minimum cost in an Undirected Graph $G=(V,E)$ that has nonnegative integer cost $c(u,v)$ associated with each edge $(u,v)\in E$.

This problem is usually simplified by assuming the Triangle Inequality, e.g. by Approx TSP Tour.

Theorems

Approximation Computability

If P ≠ NP, then for any constant $\rho \ge 1$, there is no polynomial-time Approximation Algorithm with Approximation Ratio $\rho$ for the Traveling-salesman problem without assuming the Triangle Inequality.

Proof

See CLRS p. 1115.