Euclidian TSP and the Higway problem are two of the best studied NP-Hard problems in computer science. My intention with this report is to investigate the path of research from papers where a $O(\log n), \epsilon \approx 0.874$ was proposed to some more recent research which imporoves this to $O(\log n\ / \log \log n)$
Similarly for the Euclidian TSP, I hope to study the initial simple approximation algorithim with a $O(n^{20m + 5}), \epsilon = \frac{c}{m}$ where c is some constant factor pertaining to the graph (1, $\sqrt{2}$) and $m$ is the number of "guillotines" required in the solution of the problem to current schemes which are $O(n^{(log n)O(c)}), \epsilon = 1 + \frac{1}{c}$, which are nearly constant time.
The tools that I'll be using to answer and visualize these methods are those we've been using in this class all along, as well as real-world and artificailly created graph datasets to run them on. This should provide me with a set of nice complexity curves that show the improvement in algorithims over the years, and pertinient visualizations to how the algorithims work inside. (The $m$-guillotine one lends itself particularly well to visualization)
After discussion with the teaching team, it seems the best way forward is to proceed with several solvers for Euc-TSP, both agent and heuristic based, and evaluate them based on a complexity vs performance basis.
In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is choosing weights so as to maximize the profit.
The Euclidian TSP is a equivalent-hardness special case of the TSP, where graph nodes are located in $\mathbf{R}^n$, so the trangle inequality always is true. It's the most researched one too.
https://arxiv.org/pdf/1004.3051.pdf : Prizing on Paths: A PTAS for the Highway Problem. One of the better implementations of the Highway problem
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.165.7929&rep=rep1&type=pdf : Improved Orientations of Physical Networks. The best implementation of the Highway problem, original paper, and how given a few assumptions we can reduce some cases to $O(polylog(n))$ time.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.6594&rep=rep1&type=pdf : Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. The best (comprehensible) Euclidian TSP paper
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.4805&rep=rep1&type=pdf : Guillotine subdivisions approximate polygonal subdivisions: Part II - A simple polynomial-time approximation scheme for geometric k-MST, TSP, and related problems. THe original paper regarting PTAS's for Euclidian TSP
In [ ]: