COMP 280 — Extra Credit 4

You are the new regional salesperson for Wile E.'s Widgets, a subsidiary of the Acme Corporation, and it is your job to drive around Texas to all the Widgets-R-Us superstores to check on our in-store promotions. As is frequently the case, we can trade time for money. We don't want to wait for a slow algorithm to find the absolute best tour, but can we quickly find a pretty good tour? Your boss, Mr. Coyote, tells you that your gas budget can be up to twice the absolute minimum if you leave now.

Find and explain a polynomial-time algorithm that always finds a tour cost that is at most twice the minimum. Finding the minimum, which is the Traveling Salesman Problem, is very hard to solve as far as we know. All existing solutions require exponential time and are little better than trying all tours among the cities.

• You get to assume that the distances between cities obey the triangle inequality — e.g., the distance from Houston to Dallas via Tomball is no more than going direct. That's always the case for roads, anyway.
• Hint: Start by finding a spanning tree.

As a reminder, the Traveling Salesman Problem asks us to find the shortest tour of all the cities (that have a Widgets-R-Us) on a map.

• Map — a complete undirected graph with a distance for each edge
• Cities — the vertices of the graph
• Tour — a path going through all of the cities exactly once, ending where it starts
• Shortest — having lowest total distance of edges in the path