Communications of the ACM
Computer Scientists Break Traveling Salesperson Record
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