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.
Theoretical computer scientist Shayan Oveis Gharan, an assistant professor at the University of Washington in Seattle, has made