The best algorithm for finding an approximate solution to the difficult mathematical problem 'Traveling Salesman Problem' is updated for the first time in decades

The traveling salesman problem is a difficult mathematical problem in which a salesman traveling in multiple cities travels through all cities exactly once and seeks the route with the lowest total travel cost. For many years, ' Christofeed's algorithm ' has been regarded as the algorithm with the highest approximation of the traveling salesman problem, but a new paper 'It has been proved that there is an algorithm with a degree of approximation that exceeds Christofides' algorithm' , Computer science researchers have announced.

[2007.01409] A (Slightly) Improved Approximation Algorithm for Metric TSP
https://arxiv.org/abs/2007.01409

Computer Scientists Break Traveling Salesperson Record | Quanta Magazine
https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/

The traveling salesman problem is one of the basic problems that many theoretical computer scientists have been working on. Many scientists think that there is no algorithm for the traveling salesman problem that finds a truly optimal solution that is not an approximate solution, but research has been carried out in search of the best algorithm. Regarding the enthusiasm of these scientists, Christos Papadimitriou, a leader in computational complexity theory , describes the traveling salesman problem as 'this is not a'problem'but an'addiction'.'

Years of research have devised a variety of methods for finding approximate solutions, including local search algorithms , simulated annealing , and genetic algorithms . Among them, the Christofides algorithm discovered in 1976 can find 'an approximate solution that is up to 50% longer than the best path' and has been regarded as the best algorithm for decades. It was.

Computer science researchers at the time Christofides' algorithm was announced thought that soon someone would improve it and discover a more accurate algorithm. However, despite decades of effort, no algorithm was found that surpassed Christofides' algorithm.

'Everyone knows a simple algorithm, know it,' said Alantha Newman, a researcher at the University of Grenoble Alps, about how Christofides' algorithm has been the best algorithm for finding approximate solutions for many years. If you do, you know the cutting edge. '

In 2010, a team of researchers at Georgia Institute of Technology, including Amin Saberi, Shayan Oveis Gharan, and Mohit Singh, developed a new algorithm that improved Christofides' algorithm. Intuitively, the new algorithm, which allows for more efficient exploration of parts of the path, seemed to be more efficient than the previous method. However, proving that 'the new algorithm is more efficient than Christofides' algorithm' was a new challenge.

In 2011, Saberi and colleagues proved that the new algorithm outperforms Christofides' algorithm in a limited range of traveling salesman problems. However, it seems that this proof could not be extended to the general traveling salesman problem and remained for nearly 10 years.

But Oveis Gharan continued to think, 'Even in the general traveling salesman problem, our algorithm should be better than Christofides' algorithm.' Oveis Gharan suspected that there might be proof clues in a field called geometry of polynomials, which is little known in the world of theoretical computer science.

Meanwhile, an excellent graduate student named Nathan Klein entered the laboratory of Mr. Oveis Gharan who moved to the University of Washington. Asked for advice on what to study with his instructor, Professor Anna Karlin, Oveis Gharan invited him to work with him on the algorithms for the traveling salesman problem that he had been thinking about for years. At that time, Mr. Klein accepted the proposal because he thought that he could learn a lot in the process even if the problem could not be solved. 'I didn't think I could really solve this problem,' said professor Karlin.

In the first year, the research team worked on solving a more simplified version of the problem and understood the challenges they were facing. After that, as a result of continuing to work on an approach based on the geometry of polynomials, finally, 'The algorithm devised 10 years ago is an approximate solution to the general traveling salesman problem with slightly higher accuracy than Christofides' algorithm. Can be sought. ' The paper has not been peer-reviewed, but experts are convinced that it is correct.

As a result of the analysis, it was found that the new algorithm exceeds Christofides' algorithm by a small number of '0.2 billionth of a trillionth of a trillionth of a percent (0.0000000000000000000000000000000002%)'. However, the research team expects this to be a major step forward in the traveling salesman problem, breaking through not only theoretical but also psychological barriers. Oveis Gharan said he sent an e-mail to his former instructor, Amin Saberi, when the dissertation was completed, jokingly saying, 'I think I can finally graduate.'