Minimum Spanning Trees for 2-approximation of metric Travelling Salesman Problem
Advanced Algorithms, Spring 2021
- Make a working implementation of a 2-approximation algorithm for the TSP using the Minimum Spanning Tree (MST) approach discussed in class. (We are providing starter code and tests).
- Make a brute-force implementation to find the true optimal solution to the TSP.
- Show that the MST approach is truly a 2-approximation with respect to the optimal solution found via brute-force.
Tests are provided at the end of the provided scaffold file. At a minimum, your code should pass all of the tests in that file. The code is directly drawn from the work seen here. Naturally, this means that the answer to the question is also at that link - we ask that you don't look at the solution unless you feel absolutely necessary (honor code!).
In the starter code, we've provided an implementation for the Minimum Spanning Tree (MST) algorithm, among other functions, to speed up your coding work. In case you need a refresher on how such an implementation would look like, you might find it helpful to take a look at this reference.