Inexact Remarks On Exact TSP Algorithms

An interesting approach to TSP‽

Michael Held is a mathematician who was at IBM Yorktown Research in the 1960’s, and worked with Dick Karp who was also there at the time. Held has worked on a variety of things, but is best known in complexity theory for the the famous work he did with Dick on the Travelling Salesman Problem (TSP).

Today I want to talk about an approach to the TSP problem that should be better known. It might be new, or it might be known to be blocked—but even then it may lead to future insights.

Held and Karp worked on the TSP about fifty years ago. Recall the TSP is finding a complete cycle in a weighted graph that has least cost. Here is a press release and photo from those days on their important work:

(source)

WHITE PLAINS, N.Y. Jan 2 … IBM mathematicans (left to right) Michael Held, Richard Shareshian, and Richard M. Karp review the manual describing a new computer program which provides business and industry with a practical scientific method for handling a wide variety of complex scheduling tasks. The program, available to users of the IBM 7090 and 7094 data processing systems, consists of a set of 4,500 instructions which tell the computer what to do with data fed into it. It grew out of the trio’s efforts to find solutions for a classic mathematical problem — the “Traveling Salesman” problem — whcih [sic] has long defied solution by man, or by the fastest computers he uses.

I like several things about this press release: (i) you can see the figure of the US on the back page; (ii) the program used less than five thousand instructions—today your phone has tens of millions of instructions; (iii) the release gave a short but nice description on what a program is. And finally the last part, “has long defied solution by man, or by the fastest computers he uses,” is still true today: we still do not know an efficient algorithm for TSP.

I will use the term TSP for the rest of the discussion to apply to the special case when the weights are restricted to be , which really is the Hamiltonian Cycle Problem. It also applies to the grid-graph version with Euclidean distance which we mentioned just now here. But most of what I say actually applies to the TSP with arbitrary weights. And anyway the special case is of great importance, for both theoretical and practical reasons. So TSP it is.

TSP In 1962

In 1962 I was…—never mind. Our friends at Wikipedia have a list of the key events of that year; here are my favorites:

• Wilt Chamberlain scores 100 points in a single NBA basketball game.

• The Beatles release their first single for EMI, “Love Me Do.”

• The term “personal computer” is first mentioned by the media.
• The first Walmart store, then known as Wal-Mart (which is still the corporate name), opens for business in Rogers, Arkansas.

• American advertising man Martin Speckter invents the interrobang, a new English-language punctuation mark.

The last is personal: I met Speckter, since at the time my dad, Jack Lipton, was the art director for Speckter’s ad agency. Not surprisingly my dad designed the first rendering of the new symbol for his boss—if only they had seen it become a standard symbol. Ken concurs, saying the substrings “!—?” and “?—!” appear often in his e-mails. It is Unicode U+203D and HTML glyph 8253, so perhaps that qualifies as standard.

‽

The big result of the year, of course, was neither Wilt, the Beatles, the PC, Wal-Mart, nor the interrobang; it was the first nontrivial progress ever made on TSP. In 1962 Richard Bellman and independently Held and Karp used dynamic programming to prove that a TSP problem on cities could be solved exactly in time . The dynamic programming method had been discovered and developed postwar by Bellman, and this was one of the more exciting initial applications of the method. Note that the “obvious” method of trying every sequence runs in factorial time, so this result is a huge improvement.

The idea they discovered is quite simple. Imagine that we have objects for each subset of the vertices of the graph in question, and let be a vertex. We wish to compute the following function is 1 if there is a walk from to using only the vertices from , and is 0 otherwise. If we can compute , then we will determine whether or not there is a TSP solution. Pretty simple, pretty clever.

The algorithm they discovered is quite simple—or perhaps not so simple. Even today their solution is not obvious. One indication is a long discussion last autumn on StackExchange about this algorithm. The worry was why was the polynomial factor only quadratic in ? The answer is partly that those discussing this issue were talking about a related but less efficient algorithm. In this algorithm the objects are : the value of on this object is again 0,1, but that rule is it is 1 when there is a path from to using only vertices from . This works too, but is less efficient than the Bellman-Held-Karp result.

The simple trick of fixing the start of the TSP cycle saves a factor of and is good to remember. The more general notion is to exploit any symmetry in your problem. Cycles have a simple, but powerful symmetry that is used here.

TSP Fifty Years Later

The breakthrough happened in 2010. The best Hamilton Cycle algorithm is now a randomized algorithm that runs in time where , where is about . For bipartite graphs such as the grid graphs mentioned above is about , i.e., this is roughly a -time algorithm. This is a huge result, and I have discussed it at length here. The result is due to Andreas Björklund.

I will not say much about the proof of this result—see the paper for the best insight, or look at my comments for an overview. Suffice it to say that the result could not have been proved in 1962, or even in 1972. The basic methods used in the proof were unknown then. That is progress.

The Idea

I was thinking about the TSP problem the other day, and realized there is a simple way to approach it that may yield a new algorithm. So far the method does not yield any improvement, but it does yield a very different approach. At least I think so. Let me explain the idea.

The idea is based on a connection with fast algorithms for the knapsack problem—one of my favorite algorithms—see here for a discussion on it, and here for a followup. Let and be large sets of integers, and imagine that we want to determine whether there are and so that . The “obvious” algorithm requires the product of the size of the sets, ; there of course a faster algorithm that runs in almost the sum of the sizes of the sets. Use sorting to see if and have an element in common. This is the basis of the wonderful algorithm for knapsack that runs in time multiplied by a polynomial in , where is the number of items.

The natural idea is to do better and look at the case where there are multiple sets. Suppose that , , and are are sets of integers. Now the question is: are there , , and , so that

Is there an algorithm for this that runs in time that is roughly the sum of the sizes of the sets?

If there were then we would get a knapsack problem that runs in polynomial in times . Namely, we can select any one partition of the given set of numbers into each of size about ; then for any of elements summing to a given target , taking , , and gives three subset sums , respectively, such that . So now create to be the set of sums obtained over all possible subsets for , and similarly for and from The sets each have size about and we have used time to make them.

Even if we can’t find an -time algorithm to finish the part, we could create the set of all sums from and then apply the trick for , getting time . Of course here that is not as good as dividing into halves, but we are thinking of cases where we might not have the freedom to fix an arbitrary partition. And so on for , …

The Approach

The connection that I want to raise is that TSP can be made into exactly this type of problem. I will explain it for two sets, but the idea works for three or more sets. It is just a bit simpler to explain in the case of two sets.

The objects are same as before, . The idea is to compute all of them, but only when the cardinality of the set is (less than or) equal to . We assume is even. Denote by the number of these objects: unfortunately it is still order , but we will get back to that later.

Let be the set of all the objects with value , meaning there is a path from to that goes through every node in . The key is to determine whether or not there are two objects and in so that

This is true if and only if there is a solution to the TSP.

The key is to do a simple encoding into sets. Given , we identify a subset with an -bit binary string, allowing initial padding s. Then given in binary, we denote by the number given by concatenating the string for to , and the same but complementing the bits of . Then define:

Then we look for and so that

where is the all-1 string of length . We actually subtract every element in from to use the trick from before.

The rub alas is that we are not able to cut down the search space as simply as before, because we cannot start with an arbitrary partition . The vertex subset might not be a segment of a cycle, and might not even induce a connected subgraph. We would get a little savings if we needed only to care about subsets with , but the dynamic programming method needs building up from smaller subsets.

It helps to note that the same bit-additive idea applies for breaking up into any number of subsets of ; we just need to use some extra padding on the parts. For three subsets , however, we do seem to need to consider pieces of the form as well as and . This complicates but does not prevent the padding idea, and losing a little efficiency by needing two endpoints different from the fixed is a minor annoyance.

What do we hope to gain? Perhaps for interesting graphs we can better bound the number of smaller subsets we need to consider, for instance ruling out all that induce a disconnected subgraph or a tree other than a path. For three subsets, even if we incur some redundancy that makes things work in time , that would still improve on Björklund’s result.

Open Problems

Can we use the method I outlined to get a better algorithm? I hope that the connection to other methods may be useful. After all, it’s what GLL is all about:

Helping you prove better theorems™.

Advertisements