Crazy ideas meet crazed audience

Merrill Flood was a mathematician who publicized the Traveling salesman problem TSP back in the 1940s.

He says that he found the problem while:

I was struggling with the problem in connecting with a school-bus routing study in New Jersey.

Today I thought we might look at the TSP from a viewpoint of complexity theory.

First, we note that the origins of the TSP are unclear. In 1832 it was mentioned in a handbook for traveling salesmen in Germany and Switzerland. William Hamilton talked about the related problem later named for him:

On finding a circuit through all points of graph.

Karl Menger, in the 1930s, defined the TSP, and considered the obvious brute-force algorithm, and observed the non-optimality of the nearest neighbor heuristic. We have annotated Wikipedia’s optimal-tour example to show (in blue) one case where a node is not connected to either of its two nearest neighbors in the tour and another where a mutual nearest-neighbor edge is not used in the optimal tour (the latter is a slight fib as-is but can be nudged, we believe):

Modern Times–Practice

The TSP is now well known to be NP-complete thanks to Dick Karp’s brilliant work in the 1970s. Flood would be happy to hear—we believe—that there is now a computer program Concorde that can solve TSP with many cites and get a nearly optimal solution. The authors of this program are: David Applegate, Robert Bixby, Vasek Chvatal, and William Cook.

Concorde has been applied to problems of gene mapping, protein function prediction, vehicle routing, conversion of bitmap images to continuous line drawings, scheduling ship movements for seismic surveys, and in studying the scaling properties of combinatorial optimization problems.

Modern Times–Theory

Concorde’s solutions are guaranteed to be within 2-3% of optimal and have worked for problems with tens of thousand cities or more. A lot more than Flood considered.

So why are we interested in the TSP still? A good question.

The answer is not simple. In spite of the problem’s NP-completeness and widespread belief that PNP we still do not know for sure. Could there be an algorithm that always solves TSP in polynomial time? We do not know.

We also as complexity theorists want provable algorithms, want exact algorithms, or at least approximate algorithms with provable bounds. These are lacking. This is why we were excited by the recent result of a tiny improvement to the bound on TSP by Anna Karlin, Nathan Klein, and Shayan Oveis Gharan.

Maybe we are crazy to be excited over a microscopic shaving off from . But their result comes with new ideas, and since we don’t believe that is Nature’s final answer, those ideas should yield further advances. What we are really crazy over is new ideas, and that prompts us to attempt to find another in the rest of this post. What complexity theorists do have more of than when Ken and I started is receptacles for new ideas, and we try for one in resource-bounded communication complexity.

Alice and Bob

In this spirit of craziness let’s take a complexity viewpoint of TSP. Let’s visit Alice and Bob. By the way I always have thought the invention of them by Ron Rivest, Adi Shamir, and Leonard Adleman in their 1978 RSA paper was important. This idea has probably helped improve exposition more than any other single idea.

They Meet the TSP

So suppose that Alice and Bob are presented with a city TSP. Further suppose that Alice can solve the TSP, but Bob like the rest of us cannot. An issue is:

Can Alice send a succinct message to Bob that allows him to find an optimal tour in polynomial time?

Without the word “succinct” there would be the simple answer of sending Bob her optimal tour. We will discuss a modest improvement: she can send half as many bits to Bob as it takes to describe the optimal tour. We suspect the following is known, but it suggests a possible interesting direction.

Theorem 1 (Main) Alice can send Bob a message of bits, so that he can get an optimal TSP tour in polynomial time.

This theorem holds for general TSP: it can be asymmetric and need not satisfy the triangle inequality.

The Proof

Proof: Let’s assume that ; the argument is the essentially same if is odd.

Alice will first solve the TSP exactly. Assume she finds an optimal tour that visits the cities in order

To simply the notation let be the distance from to . Then let Alice send Bob the odd cities in order

This message has the right length in bits of .

Bob receives this message and creates the following bipartite graph : The left vertices are the cities

The right vertices are

has edges connecting every left vertex to every right vertex; i.e., is the complete bipartite graph.

The first idea is that any perfect matching in extends uniquely to a tour, because Bob knows the order of the odd vertices in Alice’s tour. That is, if is an edge in the tour, then Bob knows that the next edge goes to node (modulo ).

The second idea—which is a caveat—is that an optimal matching under the graph’s original distance function might not produce Alice’s tour. For this to be true, it would need to be the case that for every optimal tour, either one of the two perfect matchings it induces would need to be an optimal matching for the tour’s odd and even vertices. An example where this fails is shown at lower left in our diagram above: The green edge is part of the optimal odd-even matching but is not in Alice’s optimal tour.

The trick is to change the distance function to include the edge that Bob must add to the tour. That is, we give the edge the cost

Note has edges connecting every left vertex to every right vertex; i.e., is the complete bipartite graph.

Bob then finds a minimum cost matching for the graph . This can be done in polynomial time. We claim the following:

1. The matching

   

   has the cost of the original TSP tour.

2. Every minimum complete matching of yields a tour for the original TSP with the same cost as the matching.

These claims imply that Bob can solve the TSP in polynomial time.

We note that (1) follows from the definition of the graph and its costs. In order to see (2) let match to . This means that there are edges

for all . This is clearly a tour, since is a permutation by the definition of matching.

Open Problems

The fact that Alice can send only half of the tour to Bob suggests: can we avoid having Alice solve the TSP in order to compute her message? This is the direction we are interested in. If she could do that it would improve some known complexity bounds on TSP. A possible idea is:

Replace having Alice solve the city TSP exactly. Instead have her solve some randomly selected subproblem exactly, and then use the above method to add in the remaining cities.

Can this work?

We have not found something like this when searching on TSP and communication complexity, but would not be surprised if the matching idea, caveat, and trick have been noticed and remarked on before.