Shayan Oveis Gharan finds the shortest route to success

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 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.”
Oveis Gharan’s unwavering focus has enabled him to identify connections between seemingly unrelated areas of mathematics and computer science. He scrutinizes the work of the fields’ most brilliant minds and adapts those techniques to fit his purposes. This strategy — bringing new tools to old problems — is the basis for leaps he has made on two varieties of the traveling salesman problem.

“If you want to build a house, you need to have a sledgehammer and a level, a wrench, tape measure,” he says. “You need to have a lot of tools and use them one after another.” Oveis Gharan, age 30, stocks his toolkit with the latest advances in fields with obscure-sounding names, including spectral graph theory, polyhedral theory and geometry of polynomials. And in a twist that only Oveis Gharan saw coming, a recent solution to a long-standing problem originating in quantum mechanics turned out to be the missing piece to one aspect of the salesman’s puzzle.
For a salesman’s tour of five cities, there are just 12 possible routes; it’s easy enough to pick the one that will save the most gas. But for 20 cities, there are 60 quadrillion possibilities, and for 80 cities, there are more routes than the number of atoms in the observable universe. Relying on brute force — calculating the distances of all the possible routes — is intractable for all but the easiest cases. Yet no one has found a simple method that can quickly find the shortest path for any number and arrangement of cities. The quandary has real-world importance: Companies like Amazon and Uber, for example, want to ferry goods and people to many destinations in the most efficient way possible.

Growing up in his home country of Iran, Oveis Gharan discovered a natural appreciation for challenging puzzles. In middle school, he acquired a book of problems from mathematics Olympiad competitions in the Soviet Union. As a student, “I tend to be one of the slower ones,” Oveis Gharan says, noting that he was usually not the first to grasp a new theorem. But within a few years, he had doggedly plowed through the 200-page book.

The effort also provided Oveis Gharan with his first taste of tool collecting, through collaboration with classmates who joined him in working through the math problems. Oveis Gharan found that solutions come easier when many minds contribute. “Each person thinks and solves problems differently,” he 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.”

Oveis Gharan attended Sharif University of Technology in Tehran before making his first breakthroughs on the traveling salesman problem as a graduate student at Stanford University. He spent over a year cracking just one thorny facet, before moving on to a postdoctoral fellowship at the University of California, Berkeley.
Rather than attacking the problem head-on, Oveis Gharan works on approximate solutions — routes that are slightly longer than the optimal path but can be calculated in a reasonable amount of time. Since the 1970s, computer scientists have known of a strategy for quickly finding a route that is at most 50 percent longer than the shortest possible path. That record held for decades, until Oveis Gharan tackled it along with Saberi and Mohit Singh, then of McGill University in Montreal.

In a paper published in 2011, the team made what might sound like an infinitesimal improvement, shrinking the 50-percent figure by four hundredths of a trillionth of a trillionth of a trillionth of a trillionth of a percentage point. “People make fun of our paper because of that small improvement,” says Oveis Gharan, “but the thing is that in our area, the actual number is not the major question.”
Instead, the goal is to develop new ideas that can begin to crack the problem open, says Luca Trevisan, a computer scientist at Berkeley. “What’s so important is not the specific algorithm that he has devised, but that there is a whole new set of techniques that can potentially be applied to other problems.” Following the advance, other scientists revisited the traveling salesman problem, and decreased the number significantly; the selected route is now at most 40 percent longer than optimal.

To make his breakthroughs, Oveis Gharan keeps tabs on the scientific literature across a variety of mathematical fields. “Every time new papers or new techniques come out, he’s one of the first people who will pick up the paper and read it,” says Saberi. To discover tools outside his areas of expertise, Oveis Gharan poses pieces of the problem to researchers in other fields.

In 2015, Oveis Gharan and computer scientist Nima Anari, then at Berkeley, made further progress on an approximate solution for a more general, and more challenging, version of the traveling salesman problem. In this version, the distance to go from point A to point B might not be the same as going the opposite direction — a plausible situation in cities with many one-way streets. Researchers had a way to estimate the optimum tour length, but they didn’t understand how good the estimate was. Oveis Gharan and Anari showed it was exponentially better than known previously.

To make this advance, Oveis Gharan teased out connections to a seemingly unrelated problem in mathematics and quantum mechanics, known as the Kadison-Singer problem. “That was really surprising,” says computer scientist Daniel Spielman of Yale University, part of a team that solved the Kadison-Singer problem in 2013. “There was no obvious connection,” he says. “Shayan is incredibly brilliant and incredibly creative.”

Oveis Gharan is now focused on a furtherconquest of this version of the traveling salesman problem. Though his new advance helps approximate the optimal tour length, it can’t identify the corresponding route. Next, Oveis Gharan would like to produce an algorithm that can navigate the correct course.

You can bet he’ll continue to add to his tool collection by sampling from related mathematical and computational fields. “The grand plan is: Try to better understand how these different areas are connected to one another,” Oveis Gharan says. “There are many big open problems lying in this intersection.”