A TSP Breakthrough

A new approximation algorithm

Composite of src1, src2, src3

Ola Svensson, Jakub Tarnawski, and László Végh have made a breakthrough in the area of approximation algorithms. Tarnawski is a student of Svensson at EPFL in Lausanne—they have another paper in FOCS on matchings to note—while Végh was a postdoc at Georgia Tech six years ago and is now at the London School of Economics.

Today Ken and I want to highlight their wonderful new result.

Svensson, Tarnawski, and Végh (STV) have created a constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). This solves a long-standing open problem and is a breakthrough of the first order.

Recall that the traveling salesman problem (TSP) is the problem of finding the cheapest tour that visits all vertices of a weighted undirected graph at least once, and the ATSP allows the graph to be directed. This difference changes the problem tremendously—it also opens up new applications. Think airline routes for dates before and after the recent eclipse: the one-way fares were not symmetric.

TSP and Approximation

Below is an optimal TSP tour of 13,509 incorporated cities in the continental United States as of 1998 when it was solved. Note at bottom right that the tour includes a visit to Key West; our hearts are with all those affected by Hurricane Irma.

TSP website source

This uses the Euclidean distance. It is common to allow any metric that satisfies the triangle inequality: for any nodes , the cost of going from to is no more than that of going from to and then from to . If we have any cost function but allow the salesman to “pass through” cities already visited, we can re-define to be the minimum cost allowing transit through one or more . Then satisfies the inequality and gives the same optimum. Conversely, if satisfies the inequality then the pass-through rule is superfluous. So allowing it is equivalent to having the triangle inequality.

Without the rule or the inequality, we could take any hard instance graph of the (directed or undirected) Hamiltonian cycle (HC) problem and add some high-cost edges to get a graph . Then approximating TSP or ATSP for is equivalent to solving HC for . Assuming the triangle inequality avoids such cases and is in force for STV.

What is so interesting about the difference between the TSP and the ATSP is that a constant approximation has long been known for the TSP. Indeed, getting a factor of is easy by finding a minimum spanning tree , considering first the tour that uses the pass-through rule to travel each edge forward-and-back, and finally improves by going directly to the next unvisited vertex in that tour rather than pass through. Getting the best-known factor is based on a simple, but very clever, algorithm by Nicos Christofides. It finds a minimum-weight perfect matching for the nodes of odd degree in using the edges they induce in , creates an Euler cycle from (traversing any edge common to and twice), and finally improves as above. There has been progress on special cases—see here, but Christofides’s algorithm has withstood attempts to improve it for over forty years. Pretty impressive.

Main Theorem

The input for ATSP is a directed graph together with a . The graph is strongly connected, meaning that for all nodes there is some path from to . If there is no edge we could add one and define to be the minimum path cost as above, and so make into a complete directed graph. However, the STV paper does a series of reductions through problems in which the absence of edges matters.

For intuition, picture not a salesman but a big delivery truck doing its rounds on the one-way streets of Manhattan. By using more than one node at intersections we can model another feature of Manhattan, which is often not being able to make a left or even right turn. This makes Manhattan behave like a non-planar graph and turns the counting measure of blocks you must travel into a non-Euclidean distance, but still one obeying the triangle inequality.

Cropped from free Flickr source

Now picture an army of scooters or bicycles, each taking one or a few packages—fractions of the job. They are still subject to the road rules and cost measure (not like drone delivery which is illegal in most cities). Modeling them yields the linear programming (LP) relaxation of (A)TSP studied by Michael Held and Dick Karp, which we discussed here. Its optimum is a lower bound on the optimal amount of work for the truck.

The point is that if we can find tours with cost only a constant factor higher than then we’ve automatically achieved a constant factor approximation of . The second point is that the LPs defining , while large, are nice to analyze. So their main theorem is:

Theorem 1 There is a constant and a polynomial-time algorithm that, given any , returns a tour of cost at most .

Well, the constant proved by STV is , not “galactic” but big. What is significant is that all previous proved overheads grew as or similar in the number of nodes . Once we achieve a constant factor we can think about improving it…

The Proof Makes a Tour

We quote their summary of the proof:

We now combine the techniques and algorithms of the previous sections to obtain a constant-factor approximation algorithm for ATSP. In multiple steps, we have reduced ATSP to finding tours for vertebrate pairs. Every reduction step was polynomial, and increased the approximation factor by a constant. Hence, altogether they give a constant-factor approximation algorithm for ATSP.

See the 39-page paper the meaning of “vertebrate pair” and words like “laminarly” which we didn’t know were legal in Scrabble. They are anyway far removed from the classic vocabulary “spanning tree,” “Euler tour,” “perfect matching,” and “Hamilton cycle” which sufficed for Christofides’s still-frontline algorithm.

What we note here is their proof structure using reductions to progressively-refined problems. They use previous steps to build algorithms for each problem, with the respective names:

Yes, the subscripts of the second and fourth stand for “vertebrate” and “laminar” while the third algorithm works on a reduction of the second problem to “irreducible” instances. Each step has its own approximation ratio, whose combination becomes for a customizable which they bound by .

Our point is that the proof makes a series of seemingly incremental refinements with loose ends left unvisited until we see at some step that it can “close” and finish its objective—which makes the excursion into a tour. We want to think more deeply about other potential progress of this form that may be capable of breakthroughs in our field.

Open Problems

They never claim that they are trying to optimize the factors in their reduction steps and the final constant . An obvious question that no doubt will be solved is to improve the constant. Is there a chance to get a small one?