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™.
If you could solve the a+b+c=0 problem in o(N^2) time, then you could solve many computational geometry problems faster, unless I’ve misunderstood something.
http://en.wikipedia.org/wiki/3SUM
The knapsack problem (subset-sum) and the TSP have one thing in common that most NP-hard problems don’t have: Nobody has ever found a faster deterministic and exact algorithm for solving them than the simple algorithms discovered in ancient times – in 1974 (Horowitz-Sahni) and 1962 (Held-Karp).
The reason why Dick’s idea for partitioning the set for the knapsack problem into three subsets won’t work to get an O(2^{n/3}) algorithm is because the Horowitz-Sahni partitioning idea works only because there are two sides to every equals sign, not three. So if you partition the original set into two subsets A and B, you can solve A+B=0 by subtracting B from both sides, obtaining A = -B. But if you parition the original set into three subsets A, B, and C, and try to solve A+B+C=0, wlog the best you can do is A = -B + -C, in which you can only get an O(2^{2n/3}) algorithm.
However, Dick’s idea for partitioning the vertices for the TSP will probably work for some interesting (or maybe not so interesting) graphs.
I’m sorry, I thought Dick wrote this article, but I see now that it was Pip.
It is actually Dick’s idea. This was kind-of minimal for calling it a co-authorship—I fixed some holes in the technical part of his original draft and added some more detail.
It seems that using Table-4-Sum leads to the algorithm for general TSP with running time 3.08^n and only 1.76^n space. But this result is majorated by Koivisto and Parviainen in the paper “A space-time tradeoff for permutation problems”.
It seems that using Table-4-Sum leads to the algorithm for the General TSP with 3.08^n time and only 1.76^n space. But this result is majorated by the paper “A space-time tradeoff for permutation problems”, Koivisto, Parviainen.
It is already published