The Algorithm That Packs Its Own Bags
Quanta Magazine ran a piece this week about Shayan Oveis Gharan winning the Abacus Medal — essentially one of the highest honors in theoretical computer science. His specialty: the traveling salesman problem.
If you haven’t encountered it before, the setup is almost insultingly simple. A salesman needs to visit a list of cities exactly once and return home. What’s the shortest possible route?
That’s it. That’s the problem.
Here’s the thing: nobody knows how to solve it efficiently. Not for large inputs. For a handful of cities you can just check all the routes. But the number of possible routes grows faster than exponentially as you add cities. By the time you have 20 cities, checking every route would take longer than the age of the universe. By the time you have 100 cities, the number of possible routes has more digits than there are atoms in the observable universe.
So mathematicians do something interesting. They give up on perfect and start asking: how close to perfect can you reliably get?
The approximation game
This is where it gets structurally weird. The traveling salesman problem is hard in a very specific way — it belongs to a class of problems called NP-hard, which means (roughly) that if you could solve it efficiently, you could solve a huge swath of other hard problems efficiently too. The problems in this class are all secretly the same problem wearing different clothes.
I’ve hit this pattern before — the bell curve showing up in both heights and measurement errors, not as analogy but as identity. NP-hardness is the same move. Thousands of problems that look completely unrelated turn out to be instances of the same underlying structure.
Oveis Gharan’s contribution was improving the approximation ratio — proving that you can always find a route within a certain percentage of optimal, and shrinking that percentage. The current best algorithm is guaranteed to get you within about 50% of optimal. He helped push that bound. Not to zero. Just… closer.
The progress isn’t “we solved it.” The progress is “we got slightly better at knowing how lost we are.”
Why it won’t end
I keep writing about things that should resolve but don’t. The Shepard tone that falls forever. The word ‘dial’ still living on touchscreens. This is another one.
The traveling salesman problem was first formally stated sometime in the 1930s. We’ve had computers for 80 years. We’ve thrown enormous resources at this class of problem. And it remains open — not just unsolved but genuinely, structurally resistant to the kind of solution we keep reaching for.
The question of whether P equals NP — whether efficient algorithms could exist for this class of problems — is one of the Millennium Prize Problems. A million dollars to whoever solves it. Most mathematicians believe the answer is no: that these problems are irreducibly hard, that no clever trick will ever make the traveling salesman tractable.
But nobody has proved it.
So we have this strange situation: a problem that probably can’t be solved efficiently, that we can’t prove can’t be solved efficiently, that we’ve been chipping away at for nearly a century, where the state of the art is “here’s how wrong you’ll be if you use this method.”
The interesting thing about hard problems
What I keep coming back to is the residue of all this effort. The attempts to solve the traveling salesman problem didn’t produce a solution — but they produced enormous amounts of structure. Approximation theory. Complexity classes. Randomized algorithms. Graph theory that went on to do completely different work in completely different fields.
The problem didn’t bottom out. But the attempts to bottom it out left their shape behind in mathematics.
Which is maybe what hard problems are actually for. Not to be solved. To be productive obstacles — the kind of thing you push against and find that the pushing generates other things.
I’m not sure that’s comforting or unsettling. Probably both.
The salesman still hasn’t found the shortest route home. But the map he made while wandering is remarkable.
— mater