Skip to content

A TSP Breakthrough

September 11, 2017


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 {i,j,k}, the cost {w(i,k)} of going from {i} to {k} is no more than that of going from {i} to {j} and then from {j} to {k}. If we have any cost function {w} but allow the salesman to “pass through” cities already visited, we can re-define {w'(i,k)} to be the minimum cost allowing transit through one or more {j}. Then {w'} satisfies the inequality and gives the same optimum. Conversely, if {w} 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 {G} of the (directed or undirected) Hamiltonian cycle (HC) problem and add some high-cost edges to get a graph {G'}. Then approximating TSP or ATSP for {G'} is equivalent to solving HC for {G}. 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 {2} is easy by finding a minimum spanning tree {T}, considering first the tour {C} 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 {3/2} is based on a simple, but very clever, algorithm by Nicos Christofides. It finds a minimum-weight perfect matching {M} for the nodes of odd degree in {T} using the edges they induce in {G}, creates an Euler cycle {C} from {T \cup M} (traversing any edge common to {T} and {M} twice), and finally improves {C} 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 {G} together with a {w}. The graph {G} is strongly connected, meaning that for all nodes {i,k} there is some path from {i} to {k}. If there is no edge {e = (i,k)} we could add one and define {w(e)} to be the minimum path cost as above, and so make {G} 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 {v_*(G,w)} is a lower bound on the optimal amount {v_o(G,w)} of work for the truck.

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

Theorem 1 There is a constant {C > 0} and a polynomial-time algorithm that, given any {(G,w)}, returns a tour of cost at most {C\cdot v_*(G,w)}.

Well, the constant proved by STV is {C = 5,500}, not “galactic” but big. What is significant is that all previous proved overheads grew as {\log n} or similar in the number of nodes {n}. 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:

\displaystyle  \mathcal{A}_{\mathrm{NW}} \mapsto \mathcal{A}_{\mathrm{ver}} \mapsto \mathcal{A}_{\mathrm{irr}} \mapsto \mathcal{A}_{\mathrm{lam}} \mapsto \mathcal{A}_{\mathrm{ATSP}}.

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 {5,\!472 + \epsilon''} for a customizable {\epsilon''} which they bound by {28}.

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 {5,\!500}. An obvious question that no doubt will be solved is to improve the constant. Is there a chance to get a small one?

Advertisements
8 Comments leave one →
  1. September 12, 2017 1:10 pm

    László Végh is speaking about it right now at Simons (live streamed) https://simons.berkeley.edu/workshops/schedule/4789 and a recording will be available

    • Bibudhendu permalink
      September 13, 2017 9:02 am

      Great news!!! But explain in details.

  2. Kathryn T Farley, PhD permalink
    September 13, 2017 12:43 am

    9/12/2017
    Happy birthday, Ken, and many more. Keep up the great work.
    -Kathryn

  3. September 13, 2017 8:35 pm

    TSP is probably nearly the best NP complete problem to illustrate the theory to amateurs. 🙂 wondering if any of the genius of this proof could be imported into other problems…

  4. September 17, 2017 5:49 am

    so is there a lower bound on the approximation factor? Obviously the first query is can the approximation factor be as low as $1$?

    • j.c. permalink
      September 17, 2017 2:19 pm

      After the statement of Theorem 1.1 in the paper, the authors write:

      We remark that we have not optimized the constant of the approximation guarantee,
      in favor of simplicity. However, we believe that further developments are needed to get
      close to the lower bound of 2 on the integrality gap [CGK06] and the inapproximability
      of 75/74 [KLS13]. See the conclusions (Section 9) for further discussion and open
      problems.

      [CGK06] Moses Charikar, Michel X. Goemans, and Howard J. Karloff. On the integrality
      ratio for the asymmetric traveling salesman problem. Math. Oper. Res., 31(2):245–
      252, 2006.

      [KLS13] Marek Karpinski, Michael Lampis, and Richard Schmied. New inapproximability
      bounds for TSP. In Algorithms and Computation – 24th International Symposium,
      ISAAC 2013, pages 568–578, 2013

Trackbacks

  1. Du nouveau dans le problème du voyageur de commerce! | L'Endormitoire
  2. Salesmen math revisited – The Square Root

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s