Broad mathematical toolkit had led to key advances in the traveling salesman problem
Dennis Wise/University of Washington
Shayan Oveis Gharan, 30
Theoretical computer scientist
University of Washington
It’s a problem that sounds simple, but the best minds in mathematics have puzzled over it for generations: A salesman wants to hawk his wares in several cities and return home when he’s done. If he’s only visiting a handful of places, it’s easy for him to schedule his visits to create the shortest round-trip route. But the task rapidly becomes unwieldy as the number of destinations increases, ballooning the number of possible routes.