Anyone has solved the Travelling Salesman algorithm?

Decision and strategy, simulations and probability models, card and board games, ...
Post Reply
lalen09
Posts: 1
Joined: Tue Jan 28, 2020 10:52 am

Anyone has solved the Travelling Salesman algorithm?

Post by lalen09 »

Anyone has solved the Travelling Salesman algorithm?
User avatar
ConstantClover
Posts: 3
Joined: Sun Dec 06, 2020 10:21 pm

Re: Anyone has solved the Travelling Salesman algorithm?

Post by ConstantClover »

Recently three mathematicians at the University of Washington (Nathan Klein, Anna Karlin, Shayan Oveis Gharan) managed to improve on Nicos Christofides' 1976 algorithm in which "round trips that are at most 50% longer than the best round trip". The Klein-Karlin-Gharan algorithm shaves "0.2 billionth of a trillionth of a trillionth of a percent" off the 50% mark.
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.
Erica Klarreich, Quanta Magazine (08-Oct-2020)
https://www.quantamagazine.org/computer ... -20201008/
Post Reply