Page 1 of 1
Anyone has solved the Travelling Salesman algorithm?
Posted: Tue Jan 28, 2020 10:57 am
by lalen09
Anyone has solved the Travelling Salesman algorithm?
Re: Anyone has solved the Travelling Salesman algorithm?
Posted: Sun Dec 06, 2020 11:12 pm
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/