Galactic algorithm: Difference between revisions

Revision as of 07:22, 24 August 2022

Revision as of 21:42, 24 August 2022

Line 33:

=== Traveling salesman problem ===

For several decades, the best known approximation to the [[traveling salesman problem]] in a [[metric space]] was the very simple [[Christofides algorithm]] which produced a path at most 50% longer than the optimum. (Many other algorithms could ''usually'' do much better, but could not provably do so.) In 2020, a newer and much more complex algorithm was discovered that can beat this by <math>10^{-34}</math> percent.<ref>{{cite arXiv |eprint=2007.01409 |class=cs.DS |title=A (Slightly) Improved Approximation Algorithm for Metric TSP |author1=Anna R. Karlin |author2=Nathan Klein |author3=Shayan Oveis Gharan |date=September 1, 2020}}</ref> Although no one will ever switch to this algorithm for its very slight worst-case improvement, it is still considered important because "this minuscule improvement breaks through both a theoretical logjam and a psychological one".<ref>{{cite web |author=Klarreich |first=Erica |date=8 October 2020 |title=Computer Scientists Break Traveling Salesperson Record |url=https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/ |titlewebsite=Computer Scientists BreakQuanta Traveling Salesperson Record |author=Erica Klarreich |date=October 8, 2020Magazine}}</ref>

=== Hutter search ===