“This is a result I have wanted all my career,” said David Williamson of Cornell University, who has been studying the traveling salesperson problem since the 1980s.
The traveling salesperson problem is one of a handful of foundational problems that theoretical computer scientists turn to again and again to test the limits of efficient computation. The new result “is the first step towards showing that the frontiers of efficient computation are in fact better than what we thought,” Williamson said.
Fractional Progress
While there is probably no efficient method that always finds the shortest trip, it is possible to find something almost as good: the shortest tree connecting all the cities, meaning a network of connections (or “edges”) with no closed loops. Christofides’ algorithm uses this tree as the backbone for a round-trip tour, adding extra edges to convert it into a round trip.
Any round-trip route must have an even number of edges into each city, since every arrival is followed by a departure. It turns out that the reverse is also true — if every city in a network has an even number of connections then the edges of the network must trace a round trip.
The shortest tree connecting all the cities lacks this evenness property, since any city at the end of a branch has just one connection to another city. So to turn the shortest tree into a round trip, Christofides (who died last year) found the best way to connect pairs of cities that have odd numbers of edges. Then he proved that the resulting round trip will never be more than 50% longer than the best possible round trip.
In doing so, he devised perhaps the most famous approximation algorithm in theoretical computer science — one that usually forms the first example in textbooks and courses.
“Everybody knows the simple algorithm,” said Alantha Newman of Grenoble Alpes University and the National Center for Scientific Research in France. And when you know it, she said, “you know the state of the art” — at least, you did until this past July.
Computer scientists have long suspected that there should be an approximation algorithm that outperforms Christofides’ algorithm. After all, his simple and intuitive algorithm isn’t always such an effective way to design a traveling salesperson route, since the shortest tree connecting the cities may not be the best backbone you could choose. For instance, if this tree has many branches, each city at the end of a branch will need to be matched with another city, potentially forming lots of expensive new connections.
In 2010, Oveis Gharan, Saberi and Mohit Singh of the Georgia Institute of Technology started wondering if it might be possible to improve on Christofides’ algorithm by choosing not the shortest tree connecting all the cities, but a random tree from a carefully chosen collection. They took inspiration from an alternate version of the traveling salesperson problem in which you are allowed to travel along a combination of paths — maybe you get to Denver via 3/4 of the route from Chicago to Denver plus 1/4 of the route from Los Angeles to Denver.
Unlike the regular traveling salesperson problem, this fractional problem can be solved efficiently. And while fractional routes don’t make physical sense, computer scientists have long believed that the best fractional route should be a rough guide to the contours of good ordinary routes.
So to create their algorithm, Oveis Gharan, Saberi and Singh defined a random process that picks a tree connecting all the cities, so that the probability that a given edge is in the tree equals that edge’s fraction in the best fractional route. There are many such random processes, so the researchers chose one that tends to produce trees with many evenly connected cities. After this random process spits out a specific tree, their algorithm plugs it into Christofides’ scheme for matching cities with odd numbers of edges, to convert it into a round trip.
This method seemed promising, not just to the three researchers but to other computer scientists. “The intuition is simple,” said Ola Svensson of the Swiss Federal Institute of Technology Lausanne. But “to prove it turns out to be a different beast.”
The following year, though, Oveis Gharan, Saberi and Singh managed to prove that their algorithm beats Christofides’ algorithm for “graphical” traveling salesperson problems — ones where the distances between cities are represented by a network (not necessarily including all connections) in which every edge has the same length. But the researchers couldn’t figure out how to extend their result to the general traveling salesperson problem, in which some edges may be vastly longer than others.
“If we have to add a super expensive edge to the matching then we’re screwed, basically,” Karlin said.
Pushing Back
Nevertheless, Oveis Gharan emerged from that collaboration with an unshakable belief that their algorithm should beat Christofides’ algorithm for the general traveling salesperson problem. “I never had a doubt,” he said.
Oveis Gharan kept turning the problem over in his mind over the years that followed. He suspected that a mathematical discipline called the geometry of polynomials, little known in the theoretical computer science world, might have the tools he needed. So when Karlin came to him two years ago suggesting that they co-advise a brilliant new graduate student named Nathan Klein who had double-majored in math and cello, he said, “OK, let’s give it a try — I have this interesting problem.”
Karlin thought that, if nothing else, it would be a fun opportunity to learn more about the geometry of polynomials. “I really didn’t think we would be able to solve this problem,” she said.
She and Oveis Gharan had no hesitation about throwing Klein into the deep end of computer science research. Oveis Gharan had himself cut his teeth on the traveling salesperson problem as a graduate student back in 2010. And the two advisers agreed about the merits of assigning hard problems to graduate students, especially during their first couple of years, when they are not under pressure to get results.
The three dived into an intense collaboration. “It’s all I was thinking about for two years,” Klein said.
They spent the first year solving a simplified version of the problem, to get a sense of the challenges they were facing. But even after they accomplished that, the general case still felt like a “moonshot,” Klein said.
Still, they had gotten a feel for their tools — in particular, the geometry of polynomials. A polynomial is a combination of terms made out of numbers and variables raised to powers, such as 3x2y + 8xz7. To study the traveling salesperson problem, the researchers distilled a map of cities down to a polynomial that had one variable for each edge between cities, and one term for each tree that could connect all the cities. Numerical factors then weighted these terms to reflect each edge’s value in the fractional solution to the traveling salesperson problem.
This polynomial, they found, has a coveted property called “real stability,” which means that the complex numbers that make the polynomial evaluate to zero never lie in the upper half of the complex plane. The nice thing about real stability is that it stays in force even when you make many kinds of changes to your polynomial. So, for example, if the researchers wanted to focus on particular cities, they could use a single variable to represent all the different edges leading into a city, and they could set the variables for edges they didn’t care about equal to 1. As they manipulated these simplified polynomials, the results of their manipulations still had real stability, opening the door to a wide assortment of techniques.
This approach enabled the researchers to get a handle on questions like how often the algorithm would be forced to connect two distant cities. In a nearly 80-page analysis, they managed to show that the algorithm beats out Christofides’ algorithm for the general traveling salesperson problem (the paper has yet to be peer-reviewed, but experts are confident that it’s correct). Once the paper was completed, Oveis Gharan dashed off an email to Saberi, his old doctoral adviser. “I guess I can finally graduate,” he joked.