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.
If the previous best algorithm finds a path of 13.77 billion years (i.e. the age of universe) for some poor salesmen to travel, then the new algorithm will save him 6.27*10^-19 seconds, which is still 100 times smaller than smallest time interval measurable by human in 2010.