Informatics Specialists Go Untrodden

After decades of stagnation, new shortcuts have been found for the traveling salesman task.

Not so long ago, a team of researchers from Stanford and McGill University broke a 35-year record in computer science by an unimaginably small amount — by four hundredths of a trillionth trillionths of a percent. The breakthrough — made in the classical informatics task of the traveling salesman — was too small for any practical significance, but he breathed new life into the search for improved approximate solutions.

The task is formed as follows: for a set of cities connected by roads, it is necessary to find the shortest way to visit each city and return to the starting point. Solutions to the problem have practical applications from drilling holes in printed circuit boards to managing the schedule of tasks on a computer and organizing the properties of the genome.

The traveling salesman problem is easy to formulate, and — in theory — easy to solve by checking all possible closed paths to find the shortest path. The problem with the brute force approach is that as the number of cities grows, the corresponding number of ways very quickly begins to exceed the capabilities of the fastest computers. For ten cities there are more than 300,000 paths. For 15 cities, their number increases to 87 billion.
')

Christofides algorithm

In the early computer era, mathematicians hoped that someone would find a convenient approach to the problem — an algorithm that would solve it in a reasonable time. But although programmers made progress in specific cases — defining the shortest path for 49 cities in the 1950s, for 2392 cities in the 1980s and for 85900 cities in 2006 — no one proposed an algorithm that effectively solves the problem in the general case. According to the remarkable work of 1972, it is possible that such an algorithm does not exist at all. Informatics specialist Richard Karp of the University of California at Berkeley showed that the traveling salesman problem is NP-complete, which means that there is no effective algorithm (unless no one can prove that P = NP - but most scientists believe that this is not the case) .


The shortest way through all 13,509 US cities, whose population exceeds 500 people (according to 1998 data)

After Karp's work was published, many computer scientists began developing an efficient algorithm for finding approximate solutions to the problem — closed paths whose length is only slightly longer than the shortest. And here they were more fortunate - in 1976, Nikos Christofides, a professor at Imperial College London, developed an algorithm that yields ways that are guaranteed not to exceed the shortest path by more than 50%.

After its creation, many scientists decided that this algorithm, simple enough for students to study in an hour, will become an intermediate link, after which a more complex, better approximating true solution will be found. But decades later such algorithms did not appear.

“Almost all computer science students have spent weeks or months trying to improve the algorithm of Christofides,” says Sanjeev Arora, a scientist at Princeton University.

Finally, in 2011, the Stanford and McGill team advanced beyond the 50% guarantee for certain types of traveling salesman problems and showed that their solutions would exceed the shortest path by no more than 49.9999999999999999999999999999999999999999999996%.

Since then, a number of improved approximate algorithms have appeared, thanks to a fresh look at the problem. And while these approximations are applicable only to certain types of traveling salesman problems, their approach is quite promising, according to Michael Gomans, an informatics specialist from the Massachusetts Institute of Technology.

“We only touched the surface slightly,” he says. “I believe that maybe in five years we will achieve more impressive results.”

Shortest tree

Mona Lisa as a way between 100,000 cities

The algorithm of Christofides does not begin with the search for the shortest path, but with the search for the minimum spanning tree - a set of branches connecting cities without closed loops. Unlike the shortest path, the minimum spanning tree is fairly easy to build - you need to start by finding the shortest path between the two cities; this will be the first branch. To add the next one, you need to find the shortest path between the new city and one of the two previous ones - and so on, until all the cities are covered.

The resulting tree is not one of the possible solutions to the traveling salesman problem, since it does not give us a closed path. But it can be turned into such a path, imagining that the branches are walls, and then walking along the tree so that your finger touches the wall until you come to the beginning. The resulting walk passes through each city and comes back, but usually it is far from the shortest path, as it passes through the same segments many times - we pass each wall in the tree twice, one time from each side.

But the resulting path is at least twice as long as the shortest path. By adding branches in a special way and applying a few tricks, Christofides showed how to cut this path so that it does not exceed the shortest by more than 50%.

The minimum spanning tree is a natural starting point for building a short workaround. But this approach also became the starting point for researchers who tried to shrink Christophedes’s 50% guarantee. After all, although the minimum spanning tree first looks efficient, other trees may be better suited to the process of converting trees to a workaround — for example, you only need to add one segment of the path to a tree so that it becomes a workaround.

So the goal was to find a tree that balances length and simple conversion to a workaround. There are no efficient algorithms for searching for an ideal tree (if P = NP is not true), but a successful approximate algorithm needs only to find a good enough one.

Fractional journey

The path to a “good enough” tree included a popular, albeit counterintuitive, technique that recognizes fractional solutions for specific tasks. For example, a fractional workaround may include traveling up to half way between Minneapolis and Detroit, and up to half way between Cleveland and Detroit. From a practical point of view, this path does not make sense. But it can be accurately described mathematically, and in contrast to the classical traveling salesman problem, such a fractional version can be solved effectively.

Many computerized approximation problems can be solved by counting solutions for the fractional version of the problem, and then intelligently rounding the fractions to get an approximate solution to the original problem. But until recently, no one has yet figured out how to do this in the case of the traveling salesman problem.

In 2009, Amin Saberi from Stanford University and Arash Asadpour, then a graduate student, developed a general rounding scheme using random numbers to select an integer solution that preserves as many fractional properties as possible. Saberi believed that this scheme resembles a "heavy hammer in search of a nail." And he suspected that the traveling salesman problem might be the right nail.

A few months later, Saberi, Asadpur, Gomans, Stanford graduate student Shayan Gharan and Aleksander Madry, now working at the Federal Polytechnic School of Lausanne in Switzerland, showed that the new rounding technique can provide a good approximate algorithm for one of the options traveling salesman problem, "asymmetric" case. A year later, Saberi, Garan and Mohit Singh [Mohit Singh] from McGill University used the same approach to develop a new approximate algorithm for the usual traveling salesman problem.


The largest traveling salesman problem solved was the path between 85,900 cities, calculated in 2006. The location of the “cities” corresponds to the design of a specific computer chip created at Bell’s laboratory, and the solution is the shortest path for a laser cutting it out.

Having received a map of cities and paths, the new algorithm begins by calculating the exact fractional solution of the traveling salesman problem. He then rounds this solution to a spanning tree, which theoretically should be close to the balance between length and simple conversion to a workaround. Finally, the algorithm includes this tree — and not the minimum spanning tree — in the Christofides network.

The new algorithm was “an idea that we could have explained in a couple of hours, but its proof took about a year,” says Sabery.

After a long analysis, the Stanford / McGill team was able to improve the algorithm of Christofides by a small fraction for a broad subclass of the “graphic” traveling salesman tasks. After a few months, other teams, inspired by success, used other rounding schemes to obtain algorithms for a graphical case with better approximations. The current record is 40%, which is much better than 50% of Christofides.

The graphical case “involves a lot of the same difficulties that occur in the general problem,” says Arora, adding that the diagrams working in the graphical case can also be useful for the general traveling salesman task.

Nevertheless, says Sabery, solving a general approximate traveling salesman problem will most likely require new ideas. “Mathematical discovery is like moving through a dark room. Stretch your arm and find a chair, stretch your arm and find the table, ”he says, paraphrasing the mathematician Andrew Wiles. “At some point, the hand finds the switch, and suddenly everything becomes clear. In the case of the traveling salesman’s task, even after so many jobs that have groped so many boundaries of the possible, I don’t think that we have already found this switch. ”