Master's Thesis: Empirical Comparison of Traveling Salesperson Approximation Algorithms

I finished my master's thesis! It is titled "Empirical Comparison of Traveling Salesperson Approximation Algorithms", and you can read the whole thing here. Many thanks to my advisor, Professor Daniel Frishberg, for all his help and guidance.

The thesis compares two algorithms for the traveling salesperson problem, the multifragment heuristic and what I refer to in the paper as 2-approximation, which is also sometimes referred to as the double tree algorithm. 2-approximation is a simplification of Christofides' algorithm, which I implemented in Professor Frishberg's graduate algorithms class in December of 2024 (you can read about that here. That project served as the inspiration for starting this thesis.

I've also linked the slides I presented during my thesis defense, which took me a long time to create. I am quite proud of them, as they include many visuals I created by hand (one of them is the image for this post). My thesis committee was Professor Frishberg, Professor Ka Yaw Teo, and Professor Jonathan Ventura.