Search found 1 match

by ConstantClover
Sun Dec 06, 2020 11:12 pm
Forum: Game Theory
Topic: Anyone has solved the Travelling Salesman algorithm?
Replies: 1
Views: 7472

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 &quo...