Image: Islenia Mil, Quanta Magazine
The travelling salesman problem is a famous network optimisation problem that hasn't been improved upon in forty-four years, until now! Researchers Nathan Klein, Anna Karlin and Shayan Ovies Gharan at the University of Washington have created a new algorithm that improves on the general traveling salesman problem, by 0.2 billionth of a trillionth of a trillionth of a percent! The new approach uses random selection of optimised trees and geometry of polynomials to improve on Christofides algorithm.
Source:
