Traveling Salesman

Was revisited by an old friend today, the Traveling Salesman. Specifically, the Traveling Salesman Problem, or TSP. This, of course is one of the classics from Operations Research, which is was the field of my Masters. While I've always been intrigued by the problem, I hadn't paid much attention to whether any real progress had been made on it in the last 30 years. Answer: not much. It's NP-Complete and aside from solving specific cases for larger values on n through the use of more and faster computing machinery, it's still an uncracked nut.

In Algorithms, we're approaching it not so much as a problem to be solved, but as an example of intractable problems. As such, the mathematical problems are subordinate to the computational roadblocks, so it's a different take. However, given that the vast majority of real problems are either trivial (meaning well understood with easy to look up algorithms) or NP-complete, I would think that some discussion of heuristics and optimality estimates would be in order. Doesn't look like that's where this class is going, but if you know you can't solve a problem, it makes sense to ask how good can you do?