Computer Scientists Break Traveling Salesperson Record

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, A (Slightly) Improved Approximation Algorithm for Metric TSP, arXiv:2007.01409.

Erica Klarreich, Computer Scientists Break Traveling Salesperson Record, Quanta Magazine, October 8, 2020. (Nice pictures to explain the idea)

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

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

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

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.

詳細的細節我也不太了解。不過，美國的雜誌記者真的很厲害，可以用那麼漂亮的圖形，解釋複雜的數學概念。