Planning the Best Route with Multiple Destinations Is Hard Even for Supercomputers – a New Approach Breaks a Barrier that's Stood for Nearly Half a Century

Planning the Best Route with Multiple Destinations Is Hard Even for Supercomputers – a New Approach Breaks a Barrier that's Stood for Nearly Half a Century

Computers are good at answering questions. What’s the shortest route from my house to Area 51? Is 8,675,309 a prime number? How many teaspoons in a tablespoon? For questions like these, they’ve got you covered.


There are certain innocent-sounding questions, though, that computer scientists believe computers will never be able to answer – at least not within our lifetimes. These problems are the subject of the P versus NP question, which asks whether problems whose solutions can be checked quickly can also be solved quickly. P versus NP is such a fundamental question that either designing a fast algorithm for one of these hard problems or proving you can’t would net you a cool million dollars in prize money.


My favorite hard problem is the traveling salesperson problem. Given a collection of cities, it asks: What is the most efficient route that visits all of them and returns to the starting city? To come up with practical answers in the real world, computer scientists use approximation algorithms, methods that don’t solve these problems exactly but get close enough to be helpful. Until now, the best of these algorithms, developed in 1976, guaranteed that its answers would be no worse than 50% off from the best answer.


I work on approximation algorithms as a computer scientist. My collaborators Anna Karlin and Shayan Oveis Gharan and I have found a way to beat that 50% mark, though just barely. We were able to prove that a specific approximation algorithm puts a cra ..