The Traveling Salesman Problem: Hardness & a 2-Approximation — Visualized in 7 Minutes

Can you find the cheapest round trip through n cities? The traveling salesman problem is NP-hard — and for arbitrary costs, even approximating it is hopeless. But add one assumption, the triangle inequality, and a minimum spanning tree turns into a tour that is provably within twice the optimum. From brute-force despair to the double-tree 2-approximation. In this video, we visualize: • The TSP on 5 cities: three tours traced live, and the optimum found • Why brute force dies: (n−1)!/2 tours — 10^14 years for 30 cities • α-approximation algorithms: polynomial time plus a worst-case guarantee • Sahni–Gonzalez: no constant-factor approximation for the general TSP (if P ≠ NP) • Metric TSP: checking the triangle inequality, and why shortcuts never hurt • The double-tree algorithm: MST → double the edges → Euler circuit → shortcut • The proof that the tour costs at most 2 × OPT Animated with Manim, with English narration. Chapters: 0:00 The traveling salesman problem 1:06 How hard is the TSP? 2:04 Approximation algorithms 2:44 Bad news for the general TSP 3:39 Metric TSP: the triangle inequality 4:33 The double-tree algorithm 6:04 Why at most twice the optimum? 7:13 Outro Follow us on X: https://x.com/graphgarden01 #GraphTheory #Mathematics #Algorithms #TravelingSalesman #ComputerScience