FYI: New Approximate algorithm for travelling salesman problem

[Tommi Prami 130]

https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/

[Anders Melander 1783]

3 hours ago, Tommi Prami said:

FYI: New Approximate algorithm for travelling salesman problem

Woohoo 

 

Quote

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.

Oh..,

[Tommi Prami 130]

Improvement is improvement 😄

[Lars Fosdal 1792]

The interesting part is that there is still room for improvement - and if it is a significant one - it will have huge implications.