Computer Scientists Break ‘Traveling Sailor’ Record

When nathan klein Starting graduate school two years ago, his mentors proposed a modest plan: to work together on one of the most well-known, long-standing problems in theoretical computer science.

Original story reprint with permission from Quanta magazine, In the editorial independent publication of the Simmons Foundation whose mission is to increase the public understanding of science by covering the development and trends of research in mathematics and the physical and life sciences.

Even if they did not manage to solve it, they felt, Klein would learn a lot in the process. He went on with the idea. He said, “I didn’t have to scare.” “I was just a first-year student – I don’t know what’s going on.”

Now, in a paper posted online in July, Klein and his advisors at the University of Washington, Anna Carlin and Shayan Ovis Gharan, have finally achieved a goal that computer scientists have achieved for nearly half a century: better To find a solution. Travel seller 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 fundamental developments in computer science, which help illuminate the power of techniques such as linear programming. But researchers have yet to fully explore its potential – and not for willingness to try.

The traveling salesman “is not a problem, it is an addiction” as Christos Papadimitriou, a leading expert in computational complexity.

Most computer scientists believe that there is no algorithm that can efficiently find the best solution for all possible combinations of cities. But in 1976, Nikos Christopheid came up with an algorithm that efficiently derives approximate solutions – round trips that are 50 percent longer than the best round trip. At that time, computer scientists hoped that someone would soon improve Christopheides’ simple algorithm and come closer to the true solution. But the anticipated progress was not made.

“Many people spent countless hours to improve this result,” said Amin Saberi of Stanford University.

Now Carlin, Klein, and Ovis Gharan have proved that an algorithm devised a decade ago defeats the 50 percent factor of Christopheids, although they could only reduce the 0.2 billionth of a trillion to 0.2 billion . Yet this negative correction breaks through both theoretical rationalist and psychological. Researchers hope that this will open up ways to improve flooding.

“This is the result I have wanted for my career,” said David Williamson of Cornell University.

The problem of the traveling salesman is one of the fundamental problems that theoretical computer scientists have repeated to test the limits of efficient computation. Williamson said the new result is “the first step towards showing that efficient computing fronts are indeed superior.”

Partial progress

While there is probably no efficient way to always find the shortest trip, it is possible to find almost anything: the smallest tree connecting all cities, meaning connections with no closed ends (or “edges”). Network of Christopheides’s algorithm uses this tree as the backbone for a round-trip tour, adding additional edges to convert it into a round trip.

Each round-trip route must have an equal number in each city, as there is a departure after each arrival. It turns out that the reverse is also true – if each city on the network has an equal number of connections, the edges of the network must detect a round trip.

The smallest tree connecting all cities lacks the property of this symmetry, because at the end of a branch any city has only one connection to another city. So at least to turn the tree into a round trip, Christopheides (who died last year) found the best way to connect pairs of cities whose edges are odd. He then proved that the resulting round trip would not be more than 50 percent longer than the best possible round trip.

In doing so, he designed perhaps the most well-known approximation algorithm in theoretical computer science — one that would usually become the first example in textbooks and courses.

“Everyone knows the simple algorithm,” said Alantha Newman of the University of Grenoble Alps and the National Center for Scientific Research in France. And when you know it, he said, “You know the state of the art” – at least, you did until last July.