I read the title, “Computer Scientists Break Traveling Salesperson Record,” and was excited to read more. Algorithmic analysis and improvement is the most impactful and lasting of performance optimizations. It is not my field, so the impact of the work often eludes me but I enjoy reading such articles nonetheless.
The TSP is still intractable — no surprise there. The goal rather is to find an “efficient” algorithm (ie, polynomial time) for an approximate solution. I should add: for a good approximate solution. The record part is how good is the approximate solution.
The previous record found solutions that were at within 50% of optimal (worst case, I believe). The new solution is “0.2 billionth of a trillionth of a trillionth of a percent” better than the previous. I re-read it a few times to find to make I wasn’t missing something. But that was it. This is the big news. An improvement of 0.2 x 10-9 x 10-12 x 10-12. Percent! So that is 2 x 10-1 – 9 – 12 – 12 – 2 = 10-36, which is
0.0000000000000000000000000000000000002
better.
Suppose with the previous algorithm the best solution takes 40 minutes. With the new algorithm the best solution takes only 40 minutes. Makes one think, doesn’t it. Once again the impact of this research has eluded me.