The Christofides Algorithm: Approximating the Metric TSP Problem
The traveling salesman problem (TSP) is a well-studied and very hard in computer science and graph theory: Given N cities, what is the shortest path the visits all cities are returns to the starting position? In the blog post, we explore different ways to simplify and approximate a solution to the problem. The blog is interactive and contains animations of the steps of the algorithm.
