Anyone has solved the Travelling Salesman algorithm?
Anyone has solved the Travelling Salesman algorithm?
Anyone has solved the Travelling Salesman algorithm?
- ConstantClover
- Posts: 3
- Joined: Sun Dec 06, 2020 10:21 pm
Re: Anyone has solved the Travelling Salesman algorithm?
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.
https://www.quantamagazine.org/computer ... -20201008/
Erica Klarreich, Quanta Magazine (08-Oct-2020)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.
https://www.quantamagazine.org/computer ... -20201008/