Notes From the TSP Revolution

This is being cross-posted from my micro-blog, Tumbld Thoughts.

Here is a link [1] to the latest research on the traveling salesman problem (TSP). The TSP [2] involves visiting a set of cities using the shortest path possible while visiting each city only once (e.g. finding the shortest route). Recent research has demonstrated that by using the Christofides' algorithm, good approximations to an solution (at most 50% of the true shortest route) are possible [3]. Solutions to the TSP can be applied to a wide range of problems, including logistics, phylogenetic analysis, and power grid optimization.

NOTES:
[1] New directions in TSP research (website hosted by Georgia Tech). The first picture shows a TSP tour on a set of points resembling "Mona Lisa". The second picture (map of the United States) is representative of a more typical TSP problem (very large set size).

[2] The TSP is an NP-hard graph optimization problem, which requires innovative algorithmic solutions such as the Christofides algorithm or ant colony optimization (ACO). An example from the ACO literature:

Dorigo, M. and Stutzle, T.   Ant Colony Optimization: Overview and Recent Advances. In "Handbook of Metaheuristics", M. Gendreau and J.-Y. Potvin eds, International Series in Operations Research and Management Science, Springer, Berlin (2010) Chapter 8.

In a response to this post, I received this response from Minus-Five:

"Interesting article, but Christofides’ algorithm (or its analysis) is not a novelty: What’s actually new here is the discovery that it can be improved, if only by an epsilon (so far)". 

[3] Klarreich, E.   Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem. Wired Science, January 30 (2013).