Here's a more or less complete list of references for the known approximation and inapproximability bounds for TSP and its special subproblems. http://cstheory

Here's a more or less complete list of references for the known approximation and inapproximability bounds for TSP and its special subproblems. http://cstheory.stackexchange.com/questions/9241/approximation-algorithms-for-metric-tsp http://cstheory.stackexchange.com/questions/9241/approximati... One thing to note in particular is that general TSP has no non trivial approximation guarantee. Norvig's article might not stress this strongly enough, the guarantees he describes really depend on the triangle inequality. At least, I think the gap between what's possible for these two versions is deep enough to mention. Another important note is that the TSP subproblem Norvig attacks, Euclidean TSP, has much better theoretical guarantees than a 2-approximation. In fact, the problem has what's called a polynomial time approximation scheme (for a fixed dimension) allowing one to efficiently compute an approximation that is arbitrarily close to optimal. The runtime of the algorithm is something like n (log(n))^c where c depends on both the accuracy and the dimension.