Wednesday, November 10, 2010

MST-TSP Approximation Clarification

We've been getting lots of questions about this part of the lab; this is mostly our fault, as the documentation is unclear and possibly misleading.
Some clarifications:
1) When you are completing the graph, connect every two vertices with an edge whose weight is the shortest path between them (even if the vertices are adjacent, this may not be the shortest path)
2) Once you've gotten the order to visit the tour in, you should walk along the "edges" (i.e. shortest paths) in the MST to get from one vertex to another
3) Your tour should end with the start vertex, and shouldn't start with it.
Note that clarifications 1 and 2 aren't the only way to produce a "valid" tour (one that meets the spec), but hopefully explaining it this way makes it easier to understand and implement.
We are very sorry that this part of the assignment wasn't explained as well as it should have been.