“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.
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