Approximation Algorithm

Here's what we do. Given a metric TSP instance with distance function D:

• 1. Take D and treat it as the weight function for a weighted graph. Compute a minimum spanning tree (MST) of the graph. Let's say its cost is M.
• 2. Pick a node in the MST and begin walking along the edges in an inorder traversal. Make sure to skip over nodes we've already visited.
• 3. Return the list of visited nodes as the tour.