Computer Scientists Break Traveling Salesperson Record
Islenia Mil for Quanta Magazine
Introduction
When Nathan Klein started graduate school two years ago, his advisers proposed a modest plan: to work together on one of the most famous, long-standing problems in theoretical computer science.
Even if they didn’t manage to solve it, they figured, Klein would learn a lot in the process. He went along with the idea. “I didn’t know to be intimidated,” he said. “I was just a first-year grad student — I don’t know what’s going on.”
Now, in a paper posted online in July, Klein and his advisers at the University of Washington, Anna Karlin and Shayan Oveis Gharan, have finally achieved a goal computer scientists have pursued for nearly half a century: a better way to find approximate solutions to the traveling salesperson problem.
This optimization problem, which seeks the shortest (or least expensive) round trip through a collection of cities, has applications ranging from DNA sequencing to ride-sharing logistics. Over the decades, it has inspired many of the most fundamental advances in computer science, helping to illuminate the power of techniques such as linear programming. But researchers have yet to fully explore its possibilities — and not for want of trying.
The traveling salesperson problem “isn’t a problem, it’s an addiction,” as Christos Papadimitriou, a leading expert in computational complexity, is fond of saying.
Most computer scientists believe that there is no algorithm that can efficiently find the best solutions for all possible combinations of cities. But in 1976, Nicos Christofides came up with an algorithm that efficiently finds approximate solutions — round trips that are at most 50% longer than the best round trip. At the time, computer scientists expected that someone would soon improve on Christofides’ simple algorithm and come closer to the true solution. But the anticipated progress did not arrive.
“A lot of people spent countless hours trying to improve this result,” said Amin Saberi of Stanford University.
Now Karlin, Klein and Oveis Gharan have proved that an algorithm devised a decade ago beats Christofides’ 50% factor, though they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent. Yet this minuscule improvement breaks through both a theoretical logjam and a psychological one. Researchers hope that it will open the floodgates to further improvements.
Nathan Klein (top), a graduate student at the University of Washington, and his advisers, Anna Karlin and Shayan Oveis Gharan.
Nathan Klein (left), a graduate student at the University of Washington, and his advisers, Anna Karlin and Shayan Oveis Gharan.
Flora Hollifield; from “ Embracing Frustration,” with permission from Microsoft; courtesy of Shayan Gharan.
“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.
Samuel Velasco/Quanta Magazine
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.
Amin Saberi (top) of Stanford University and Mohit Singh of the Georgia Institute of Technology.
Amin Saberi (left) of Stanford University and Mohit Singh of the Georgia Institute of Technology.
Courtesy of Amin Saberi; Lance Davies
While the improvement the researchers established is vanishingly small, computer scientists hope this breakthrough will inspire rapid further progress. That’s what happened back in 2011 when Oveis Gharan, Saberi and Singh figured out the graphical case. Within a year, other researchers had come up with radically different algorithms that greatly improved the approximation factor for the graphical case, which has now been lowered to 40% instead of Christofides’ 50%.
“When they announced their result [about the graphical case], … that made us think that it’s possible. It made us work for it,” said Svensson, one of the researchers who made further progress in that case. He’s been trying for many years to beat Christofides’ algorithm for the general traveling salesperson problem. “I will try again now I know it’s possible,” he said.
Over the decades, the traveling salesperson problem has launched many new methods into prominence. Oveis Gharan hopes that it will now play that role for the geometry of polynomials, for which he has become an eager evangelist. In the decade or so since he started learning about this approach, it has helped him prove a wide range of theorems. The tool has “shaped my whole career,” he said.
The new traveling salesperson result highlights the power of this approach, Newman said. “Definitely it’s an inspiration to look at it more closely.”
Klein will now have to find a new problem to obsess over. “It’s a bit sad to lose the problem, because it just built up so many structures in my head, and now they’re all kind of gone,” he said. But he couldn’t have asked for a more satisfying introduction to computer science research. “I felt like we pushed back a little bit on something that was unknown.”
This article was reprinted on Wired.com and in Italian at le Scienze.
