Mathematics
The Traveling Salesman Problem and Approximation Algorithms
Quick fact
The number of possible routes for just 20 cities is about 1.2 quintillion – that's more than the number of grains of sand on Earth.
Why this is interesting
Imagine you're a salesperson who must visit multiple cities and return home. What's the shortest route? For a handful of cities it's easy, but add just a few more and solving it perfectly might take longer than the age of the universe.
Read the full explanation
Understanding The Traveling Salesman Problem and Approximation Algorithms
The Traveling Salesman Problem (TSP) asks: given a set of cities and the distances between them, what is the shortest closed tour that visits each city exactly once and returns to the start? You can visualize this as a map with dots (cities) and connecting lines (roads). For 3 cities, you can easily check the few possible permutations. But as you add cities, the number of possible tours grows factorially (n!). This means that checking every possible route becomes impossible even for moderate n. For example, with 20 cities, there are about 2.4×10^18 possible tours. What makes TSP tricky is that it's known to be NP-hard – meaning that the time needed to find the absolute best answer grows super fast with the number of cities. Exact algorithms exist, like brute-force or dynamic programming (Held-Karp), but they become impractical beyond a few dozen cities. So, instead of seeking perfection, we often accept a near-optimal solution, which is where approximation algorithms come in. These are clever strategies that guarantee a route that is at most a certain factor longer than the optimal one, but they run quickly even for thousands of cities.
A deeper explanation
The reason TSP is so hard is that it embodies the 'combinatorial explosion' common in NP-hard problems. To solve it exactly, you'd have to explore an exponentially large search space. Approximation algorithms trade off exactness for speed. They rely on mathematical properties, like the triangle inequality (which says going directly from A to C is never longer than going A to B to C). For metric TSP (where distances satisfy the triangle inequality), there's a famous algorithm by Christofides that guarantees a tour at most 1.5 times the optimal. A simpler approach: build a minimum spanning tree (MST), then traverse its edges to produce a tour (doubling edges) – this yields a 2-approximation. These algorithms work because they create a shortcut around the tree, and the MST is a lower bound for the optimal tour (since removing one edge from an optimal tour gives a spanning tree). Beyond these, there are practical heuristics like the nearest neighbor (greedy), 2-opt, and genetic algorithms that usually find very good tours, even if they don't have a theoretical guarantee. Understanding TSP and approximation reveals a core trade-off in computer science: optimality versus efficiency, and it connects to many real-world applications such as logistics, circuit design, and genome sequencing.