UW CSE professor Shayan Oveis Gharan was named one of 10 Scientists to Watch by Science News this week. The list celebrates early- and mid-career scientists under the age of 40 who are well on their way to transforming their respective fields. Oveis Gharan, a member of UW CSE’s Theory group, was featured for his contributions to solving the infamous traveling salesman problem.
From the article:
“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…has made record-breaking advances on this puzzle, known as the traveling salesman problem. The problem is famous in mathematical circles for being deceptively easy to describe but difficult to solve. But Oveis Gharan has persisted. ‘He is relentless,’ says Amin Saberi of Stanford University, Oveis Gharan’s former Ph.D. adviser. ‘He just doesn’t give up.'”
Science News points to Oveis Gharan’s ability to take inspiration and techniques from other areas of computer science and mathematics to advance research in his own field. In one example, he and colleague Nima Anari (then of UC Berkeley) were able to draw a connection between the traveling salesman problem and what, to that point, appeared to be an unrelated problem in mathematics and quantum mechanics known as the Kadison-Singer problem.
As Oveis Gharan says, “Once someone is exposed to many different ideas and ways of thinking on a problem, that will help a lot to increase the breadth of problem-attacking directions.”
Read Science News’ full profile of Oveis Gharan here, and the full list of Scientists to Watch here.
Congratulations, Shayan!