[gizmo686]

>TSP

Travelling salesman problem? Can't you get to within a factor of 2 of optimal by constructing a minimum spanning tree:

Once you have a MST (which can be built efficiently), the total weight of the tree is a lower bound for the total distance of a TSP solution. However, you can construct a TSP path that traverses each edge of the MST twice; which means that we know that this path (which is easy to find) is at most twice the total cost of the optimal path.

[NotOscarWilde]

Your solution works only in metric spaces. In non-metric spaces (distances are arbitrary and you are forced to return a cycle, not a tour that repeats vertices) no constant-factor approximation is possible.