Traveling Salesman Problem (TSP)

Given a set P of points (e.g., a bunch of cities) and pairwise "distances" between these points, the Traveling Salesman Problem (TSP) seeks to find a shortest tour that starts from a point and visits every point exactly once and returns to the starting point. TSP is computationally very difficult; the fastest algorithms for this problem run in exponential time and there are reasons to believe that faster algorithms do not exist for TSP. A special case of TSP is the metric TSP problem in which distances satisfy the triangle inequality, i.e., for any three points p1, p2, p3, distance(p1, p3) ≤ distance(p1, p2)+distance(p2, p3). Even metric TSP is computationally difficult, but there are good approximation algorithms for metric TSP. In this homework you are required to implement a simple 2-approximation algorithm for metric TSP that is based on computing an MST.

Experiments

1. Report the following statistics on the execution of Boruvka's algorithm on the input graph:

(i) how many iterations does the algorithm take and (ii) what is the size of the smallest connected component at the end of each iteration. Recall that Boruvka's algorithm comes with the guarantee that in each iteration, the size of the smallest component, at least doubles. In practice, the size of connected components can grow much more quickly than this guarantee suggests. The point of this experiment is to understand this issue.

2. As we saw in class, the asymptotic performance of Kruskal's algorithm relies on the perfor- mance of the implementation of the Disjoint Set Union Find data structure.

If you implemented this data structure as a reverse tree with Union by depth, then the depth of the deepest tree associated with a component is a good measure of the performance of this data structure. So in this case, report the maximum depth of a reverse tree after each iteration. Note that this quantity is 1 after the first iteration of Kruskal's algorithm and it will typically remain unchanged for a number of iterations and then increase by 1.

If you implemented the Disjoint Set Union Find data structure as a shallow threaded tree with union by size, then the maximum number of times the "leader" pointer of a node is changed is a good measure of the performance of the data structure. So in this case, report the maximum number of times the "leader" pointer of a node is changed after each iteration. Note that this quantity is 1 after the first iteration of Kruskal's algorithm and it will typically remain unchanged for a number of iterations and then increase by 1.

It seems best to report these statistics in a plot with the x-axis being the iteration index and the y-axis being the measure of the data structure performance being reported.

3. Output the 127 edges in the computed MST and the weight of the computed MST.

4. After transforming the computed MST into a Traveling Salesman Tour, output the tour and its weight. So you're being asked to output the Traveling Salesman tour prior to using the 2-OPT and 3-OPT local search heuristics to improve the tour.

5. Output the Traveling Salesman Tour and its weight after using the 2-OPT local search heuris- tic.

6. Output the Traveling Salesman Tour and its weight after using the 2-OPT and 3-OPT local search heuristics.

What to Turn in

You are expected to turn in two items for this homework.

1. A single file named hw8.ext containing all your code. The extension ".ext" will of course depend on the programming language you use. Your code should be extensively documented. For example, functions should be preceded by comment blocks that tell the reader what the purpose of the function is, variable names should be suggestive of their purpose, etc. The file should also start with a listing of any bugs or issues with your code, sources you used, etc. You are not allowed to share code with classmates, but it is okay to use code available on the web, with appropriate attribution. For example, you might find it convenient to use a class that implements the max-heap data structure. This is fine, provide you carefully acknowledge your source. We will set up a dropbox on ICON for you to upload your code file. This needs to be done before class time on Tue, April 18th .

2. A single pdf file named hw8.pdf containing the results of all your experiments. You should upload this file onto the ICON dropbox and bring a printout to class on Tue, April 18th. This document should be well-formatted, should contain clear and concise text, and clearly and completely labeled plots.

Extra Credit Opportunities

1. Find an optimal Traveling Salesman tour for the given input. Given the current state of human knowledge, any algorithm that does this is bound to be some variant of brute force, taking exponential amount of time. But, there are some pretty sophisticated brute force implementations for the Traveling Salesman tour computation out there and you are welcome to download and use whatever you find. To get this extra credit, report the Traveling Salesman tour that has been computed, along with its weight. Then write a paragraph on how you found this tour, e.g., what software you downloaded, how you used it, and how long it took to find the tour.

2. Show on Google maps the MST and Traveling Salesman tours you computed for the experi- ments listed above. If you do this, then attach pictures of the MST and Traveling Salesman tours to your document hw8.pdf. You are welcome to go crazy and make a webpage, allow users to interact with these structures you're constructing, etc.