Sign In

Communications of the ACM

ACM Careers

Computer Scientists Break Traveling Salesperson Record

View as: Print Mobile App Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
group peers through drawn map-curtain

Credit: Islenia Mil / Quanta Magazine

Graduate student Nathan Klein and his advisers at the University of Washington, Anna Karlin and Shayan Oveis Gharan, have achieved a goal computer scientists have pursued for nearly half a century: a better way to find approximate solutions to the traveling salesperson problem.

The team describes their work in "A (Slightly) Improved Approximation Algorithm for Metric TSP."

Over the decades, the TSP (traveling salesperson problem) has inspired many of the most fundamental advances in computer science, helping to illuminate the power of techniques such as linear programming.

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.

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.

From Quanta Magazine
View Full Article


No entries found