Skip to content

Inexact Remarks On Exact TSP Algorithms

May 8, 2012


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 {0,1}, 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 {n} cities could be solved exactly in time {O(n^2 2^n)}. 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 {n} factorial time, so this result is a huge improvement.

The idea they discovered is quite simple. Imagine that we have objects {[S,i]} for each subset {S} of the vertices of the graph in question, and let {i} be a vertex. We wish to compute the following function {f([S,i])} is 1 if there is a walk from {1} to {i} using only the vertices from {S}, and is 0 otherwise. If we can compute {f[V,1]}, 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 {n}? The answer is partly that those discussing this issue were talking about a related but less efficient algorithm. In this algorithm the objects are {[i,S,j]}: the value of {f} on this object is again 0,1, but that rule is it is 1 when there is a path from {i} to {j} using only vertices from {S}. 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 {n} 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 {O(c^n)} where {c < 2}, where {c} is about {1.657}. For bipartite graphs such as the grid graphs mentioned above {c} is about {1.414}, i.e., this is roughly a {2^{n/2}}-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 {A} and {B} be large sets of integers, and imagine that we want to determine whether there are {a \in A} and {b \in B} so that {a + b = 0}. The “obvious” algorithm requires the product of the size of the sets, {|A| \cdot |B| }; there of course a faster algorithm that runs in almost the sum of the sizes of the sets. Use sorting to see if {A} and {-B} have an element in common. This is the basis of the wonderful algorithm for knapsack that runs in time {2^{n/2}} multiplied by a polynomial in {n}, where {n} is the number of items.

The natural idea is to do better and look at the case where there are multiple sets. Suppose that {A}, {B}, and {C} are are sets of integers. Now the question is: are there {a \in A}, {b \in B}, and {c \in C}, so that

\displaystyle  a + b + c = 0?

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 {n} times {2^{n/3}}. Namely, we can select any one partition of the given set {U} of {n} numbers into {S_1,S_2,S_3} each of size about {n/3}; then for any {I \subset S} of elements summing to a given target {t}, taking {I_1 = S_1 \cap I}, {I_2 = S_2 \cap I}, and {I_3 = S_3 \cap I} gives three subset sums {a,b,c}, respectively, such that {a + b + c = t}. So now create {A} to be the set of sums obtained over all {2^{n/3}} possible subsets {I_1} for {S_1}, and similarly {B} for {S_2} and {C} from {S_3.} The sets {A,B,C} each have size about {N = 2^{n/3}} and we have used {\tilde{O}(2^{n/3})} time to make them.

Even if we can’t find an {O(N)}-time algorithm to finish the {a+b+c=0} part, we could create the set {A_{1,2}} of all sums from {S_1 \cup S_2} and then apply the trick for {a+b=0}, getting time {\tilde{O}(2^{2n/3}) = \tilde{O}(1.5874^n)}. 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 {n/4}, {n/5}

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, {[S,k]}. The idea is to compute all of them, but only when the cardinality of the set {S} is (less than or) equal to {n/2}. We assume {n} is even. Denote by {M} the number of these objects: unfortunately it is still order {2^{n}}, but we will get back to that later.

Let {\cal O} be the set of all the objects with value {1}, meaning there is a path from {1} to {k} that goes through every node in {S}. The key is to determine whether or not there are two objects {[S,k]} and {[T,\ell]} in {\cal O} so that

\displaystyle  \begin{array}{rcl}  k &=& \ell\\ 	S \cup T &=& V \setminus \{1\}\\ 	S \cap T &=& \{k\} \\ \end{array}

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 {U = \{1,\dots,n\}}, we identify a subset {S} with an {n}-bit binary string, allowing initial padding {0}s. Then given {k \in U} in binary, we denote by {Sk} the number given by concatenating the string for {S} to {k}, and {Sk'} the same but complementing the bits of {k}. Then define:

\displaystyle  \begin{array}{rcl}  A &=& \{Sk: [S,k] \in {\cal O}\}\\ B &=& \{T\ell': [T,\ell] \in {\cal O}\} \end{array}

Then we look for {a \in A} and {b \in B} so that

\displaystyle  a + b = m,

where {m = 2^{n+\lceil{\log n}\rceil} - 1} is the all-1 string of length {n+\lceil{\log n}\rceil}. We actually subtract every element in {B} from {m} 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 {U = S \cup T}. The vertex subset {S} 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 {|S| = |T| = n/2}, 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 {U}; we just need to use some extra padding on the {k,k'} parts. For three subsets {S_1,S_2,S_3}, however, we do seem to need to consider pieces of the form {[k,S_2,\ell]} as well as {[S_1,k]} and {[S_3,\ell]}. This complicates but does not prevent the padding idea, and losing a little efficiency by needing two endpoints different from the fixed {1} 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 {\tilde{O}(2^{2n/3}) = \tilde{O}(1.5874^n)}, 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™.

8 Comments leave one →
  1. aramharrow permalink
    May 8, 2012 11:39 pm

    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

  2. Craig permalink
    May 9, 2012 10:26 am

    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.

    • Craig permalink
      May 9, 2012 10:28 am

      I’m sorry, I thought Dick wrote this article, but I see now that it was Pip.

      • May 11, 2012 10:17 pm

        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.

  3. alexgolovnev permalink
    May 10, 2012 3:51 am

    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”.

  4. Sasha permalink
    May 10, 2012 2:37 pm

    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.

  5. Evgeny permalink
    September 5, 2012 9:20 am

    It is already published
    http://www.ectrie.nl/met/pdf/MET14-3-2.pdf

Trackbacks

  1. Happy Father’s Day | Gödel's Lost Letter and P=NP

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