The general TSP (where negative edge weights are allowed) cannot be efficiently approximated (if not P = NP).
The Christofides algorithm considers are far more limited version of the TSP problem (whose decision problem is still NP-complete): the so called "metric TSP": here the edge weights form a metric on the arcs, i. e.
d(v, w) > 0 and d(u, v) + d(v, w) >= d(u, w) for all u, v, w pairwise different (where d(v, w) is the weight on the edge {v, w}).
If you restrict the metric case even further and only allow planar graphs, you get even some neat approximations. For example, there exists an O(c^(1/e^2)n) epsilon approximation scheme: http://cs.brown.edu/~pnk/publications/tsp2005.pdf
This manuscript, http://planarity.org/ , contains most of the material in a planar graph optimization course I took a few years ago.
And by the way, if you do discover this "short cut" for the TSP. AKA you can solve TSP for every case in polynomial time, your name will go down in history for the following:
1. Breaking every single encryption algorithm and brute-force security methodology.
2. Creating a strategy for completing ALL NP-Hard problems in polynomial time, millions.
3. Thousands of equations with rewards for solving them will suddenly become solvable with your smart phone. You can collect on billions in reward money.
4. You will have likely shattered some fundamental assumptions we have about what matter and energy is in this universe.
So if you did solve TSP in polynomial time, you would immediately be the most famous person in the computing world for a very very long time. I think there is a solution to P=NP, but you are going to have to toy around with the fabric of space-time itself to do so. Your algorithm will have to allocate quantities of spacetime for itself to process in, and transport the answer back through time to us. This will no doubt cause problems in subspace, but that's not our problem.. yet.
For a start one-time pad (say using XOR) is a perfectly valid encryption algorithm (and its actually used in the wild) and won't be affected a iota by P = NP. Same for Carter-Wegman.
Then:
"If P=NP, you could still have a cipher that decrypts in linear time with the key and n^1000 time without the key. So it's breakable in polynomial time, yet cryptographically secure."
I don't disagree with the fact that it would be a major discovery but I very much dispute your overgeneralization about the implication regarding cryptography : )
The Christofides algorithm considers are far more limited version of the TSP problem (whose decision problem is still NP-complete): the so called "metric TSP": here the edge weights form a metric on the arcs, i. e.
d(v, w) > 0 and d(u, v) + d(v, w) >= d(u, w) for all u, v, w pairwise different (where d(v, w) is the weight on the edge {v, w}).