This article is from WeChat official account:Big Data Digest (ID: BigDataDigest), compilation: Xu Ling, coolboy, head picture from: pixabay
Just imagine, when you first entered graduate school, your advisor suggested to you: Let’s study the most famous problem to be solved in the field of theoretical computer science. What is your mood?
But this is what Nathan Klein encountered two years ago. The problem his mentor invited him to solve was the traveling salesman problem, which is one of the fundamental problems that theoretical computer scientists are trying to solve. Aims to explore efficient computation(efficient computation) ’s limits.
Even if the problem cannot be solved, they think Klein will learn a lot in the process. Klein also accepted this idea. He said, “I didn’t know I was afraid at the time.” “I was just a first-year graduate student and I couldn’t figure out the situation.”
Fortunately, in the end Klein also graduated successfully, that is to say, They achieved the computer scienceScientists have pursued the goal of nearly half a century: a better way to find an approximate solution to the traveling salesman problem, which was elaborated in the arXiv paper published in July.
The goal of this optimization problem is to find the shortest path (or the lowest cost path) through a set of cities. The solution to this problem can be used in many applications such as DNA sequencing and shared logistics planning. For decades, this issue has inspired many fundamental advances in the field of computer science, helping to clarify the power of technologies such as linear programming. However, its potential has not been fully explored.
As Christos Papadimitriou, an expert in the field of computational complexity, said, the traveling salesman problem is “not a problem, but an addictive thing”.
Most computer scientists believe that there is no optimal solution for effectively solving the possibility of various combinations of cities. But in 1976, Nicos Christofides proposed an algorithm that can effectively find an approximate solution-the round trip is at most 50% longer than the best round trip. At that time, computer scientists expected that someone would soon be able to improve on Christofides’ simple algorithm and get closer to the real solution. But the expected progress has not come.
Stanford University professor Amin Saberi said: “Many people have spent countless hours trying to improve this result.”
Now, Karlin, Klein and Oveis Gharan have proved that an algorithm designed ten years ago is better than the 50% standard of Christofides algorithm, although it only reduces this percentage by a very small number(10^-36, 0.2 billionth of a trillionth of a trillionth of a percent). Nevertheless, progress is progress after all, and this small progress can break through the theoretical deadlock and psychological threshold. Researchers hope this will bring opportunities to achieve further improvements.
University of Washington graduate student Nathan Klein (left) and his mentors Anna Karlin and Shayan Oveis Gharan
David Williamson, a professor at Cornell University, said: “This is the goal I pursue in my career.” He has been studying the traveling salesman problem since the 1980s.
Williamson said: “This new result is the first step to prove to people that the frontier of efficient computing is actually better than we expected.”
Progress
Although there may not be an effective way to find the shortest journey, it is possible to find a good enough path: the shortest tree connecting all cities(tree) , that is, a connection (edge), without a closed loop. Christofides’ algorithm uses this tree as the backbone for round trips, and then converts it into round trips by adding additional edges.
The number of edges connecting each city on any round trip route must be an even number, because every time it arrives, there must be a departure. Facts have proved that the reverse is also true-if the number of connections in each city in the network is even, then the edges in the network must be able to achieve a round trip.
The shortest tree connecting all cities does not have this even-numbered nature, because any city at the end of the route has only one connection to another city. Therefore, in order to convert the shortest tree to a round trip, Christofides(died last year) found that the best way is to connect city pairs with odd numbers of sides . He proved that the resulting round trip will never be 50% longer than the best round trip.
In the process, he designed the most famous approximation algorithm in the field of theoretical computer science-this algorithm is usually the first mentioned in a textbook or courseexample.
Alantha Newman of the University of Grenoble-Alpes in France and the French National Center for Scientific Research said: “This simple algorithm is well known.” And when you learn it, “It is the best method currently.” — This statement was still valid until July.
For a long time, computer scientists have guessed that there should be an approximate algorithm better than Christofides’s algorithm. After all, although his algorithm is simple and intuitive, it is not always effective in designing traveling sales routes, because the shortest tree connecting cities may not be the best backbone you can choose. For example, if the tree has many branches, the city at the end of each branch needs to be matched with another city, which may form a large number of costly new connections.
In 2010, Oveis Gharan, Saberi, and Mohit Singh of the Georgia Institute of Technology began to think: Maybe instead of choosing the shortest tree connecting all cities, a random tree from a carefully selected set can be used to improve the Christofides algorithm. They were inspired by an alternative version of the traveling salesman problem, in which traveling salesman can travel along a combination of paths. For example, to get to Denver, you can add 3/4 of the route from Chicago to Denver plus the route from Los Angeles to Denver.
Different from the conventional traveling salesman problem, this fractionalization problem can be effectively solved. Although this fractional path (fractional route) is not of practical significance, computer scientists have long believed that the best fractional path can be The good general path provides rough guidance.
Therefore, in order to create their own algorithm, Oveis Gharan, Saberi, and Mohit Singh defined a random process for selecting a tree connecting all cities, and made the probability of a given edge in the tree equal to that edge at the end. The score in the best score path. There are many such random processes, and researchers tend to choose random processes that can generate trees with multiple even-numbered cities. After selecting a specific tree in this random process, they then plugged their algorithm into Christofides’ scheme, matched cities with odd numbers of sides, and transformed the result into a round trip.
Picture source: Samuel Velasco/Quanta Magazine
This method looks promising. Not only these three researchers think so, but other computer scientists also think so. Ola Svensson, associate professor at the Federal Institute of Technology in Lausanne, Switzerland, said: The intuitive understanding is very simple, but proving it is a big problem.
However, in the second year, Oveis Gharan, Saberi, and Singh successfully proved that their algorithm is superior to Christofides’s algorithm in the “Schematic” traveling salesman problem. The “Schematic” traveling salesman problem expresses the distance between cities as a network (not necessarily including all connections), in which all sides have the same length. But they failed to find a way to extend this result to the general traveling salesman problem. Some sides of the general traveling salesman problem may be much longer than others.
Karlin said: “If you add a costly edge to the match, this plan will basically be over.”
The course of progress
Nevertheless, in this collaboration, Oveis Gharan has an unshakable belief: their algorithm also outperforms the Christofides algorithm on the general traveling salesman problem. He said: “I never doubted it.”
For many years, this question continued to circulate in Oveis Gharan’s mind. He guessed that a mathematical subject called “polynomial geometry” may have the tools he needs, but this is an area that the theoretical computer science community does not pay much attention to. Therefore, when Karlin advised him to mentor Nathan Klein, a talented graduate student two years ago, he replied: “No problem, let’s try it-I happen to have an interesting question.” Nathan Klein majored in mathematics and Two majors in cello.
What Karlin thought at the time was that even if there were no results, this would be a good opportunity to learn polynomial geometry. She said: “I did think we could not solve this problem.”
She and Oveis Gharan did not hesitate to bring Klein into this deep field of computer science research. Oveis Gharan himself studied the traveling salesman problem when he was a graduate student in 2010. Both of these tutors thought it would be helpful to assign difficult problems to graduate students, especially when they hadn’t had the pressure to produce results a few years ago.
The three researchers started working closely together. Klein said: “I have been thinking about it in the past two years.”
In the first year, they solved a simplified version of the problem in order to feel the difficulty they were facing. But even after solving the simplification problem, Klein said that solving the general traveling salesman problem is still “difficult.”
Nevertheless, they have a good understanding of the tools used, especially polynomial geometry. Polynomials are power expressions, such as 3x2y+8xz7. In order to study the traveling salesman problem, they refined the map of cities into a polynomial, where each variable represents an edge between cities, and each term represents each tree that can connect all cities. Then use numerical factors to weight these items to reflect the value of each edge in the fractional solution of the traveling salesman problem.
They found that this polynomial has a characteristic they need, that is, “real stability” (real stability), which means that The complex number whose polynomial is zero will never appear in the upper half of the complex plane. The advantage of real number stability is that it still works even with many changes to the polynomial.
For example, if researchers want to focus on certain cities, they can use a single variable to represent all the different edges connecting a city, and then set the variable of the edges that they don’t care about to 1. When operating these simplified polynomials, their operating results still have real number stability, which opens the door to the application of various technologies.
This method allows researchers to deal with many questions, such as how often the algorithm is forced to connect two cities that are far apart. In nearly 80 pages of analysis, they successfully proved that the algorithm is superior to Christofides algorithm on general traveling salesman problems.(The paper has not been peer reviewed, but some experts Affirmed.)
As soon as the thesis was completed, Oveis Gharan sent an e-mail to his PhD supervisor Saberi. He joked: “I thinkI finally graduated. “
Stanford University Professor Amin Saberi (left) and Georgia Institute of Technology Mohit Singh
Although the improvement achieved by this research is minimal, computer scientists hope that this breakthrough will inspire further progress.
Look back to 2011, when Oveis Gharan, Saberi and Singh solved the schema traveling salesman problem. Less than a year later, other researchers proposed very different algorithms, which greatly improved the approximate performance of the graphical cases. Now in the schematic case, these algorithms have reduced the approximation rate (approximation factor) from 50% of Christofides algorithm to 40%.
“When they announced the results of the schema traveling salesman problem, we thought it was possible. We also started to study it.” said Svensson, a researcher who made progress on this case later. He has been trying to surpass Christofides algorithm in general traveling salesman problem for many years. He said: “Now I know it is possible, I will try again.”
In the past few decades, the traveling salesman problem has spawned many new methods. Oveis Gharan hopes that now people can see the value of polynomial geometry, and in fact he has become an enthusiastic evangelist of this method. In the last ten years or since he started learning this method, polynomial geometry has helped him prove many theorems. He said: This tool “shaped my entire career.”
The new results of the traveling salesman problem prove the power of this method. Newman said: “If you study carefully, you will definitely be inspired.”
Klein now has to find a new problem to study. “It’s a bit sad to lose this problem because it builds a lot of structure in my mind, but nowThey almost disappeared. “But his contribution to computer science research is already very satisfying.
“I feel that we have pushed the unknown a little further.”
Related reports:
https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/
This article is from WeChat official account:Big Data Digest (ID: BigDataDigest), compile: Xu Ling, coolboy