16
$\begingroup$

A recent question discussed the now-classical dynamic programming algorithm for TSP, due independently to Bellman and Held-Karp. The algorithm is universally reported to run in $O(2^n n^2)$ time. However, as one of my students recently pointed out, this running time may require an unreasonably powerful model of computation.

Here is a brief description of the algorithm. The input consists of a directed graph $G=(V,E)$ with $n$ vertices and a non-negative length function $\ell\colon E\to\mathbb{R}^+$. For any vertices $s$ and $t$, and any subset $X$ of vertices that excludes $s$ and $t$, let $L(s,X,t)$ denote the length of the shortest Hamiltonian path from $s$ to $t$ in the induced subgraph $G[X\cup\{s,t\}]$. The Bellman-Held-Karp algorithm is based on the following recurrence (or as economists and control theorists like to call it, “Bellman's equation”):

$$ L(s,X,t) = \begin{cases} \ell(s,t) & \text{if $X = \varnothing_{\strut} $} \\ \min_{v\in X}~ \big(L(s, X\setminus\lbrace v\rbrace, v) + \ell(v,t)\big) & \text{otherwise} \end{cases} $$

For any vertex $s$, the length of the optimal traveling salesman tour is $L(s,V\setminus\{s\}, s)$. Because the first parameter $s$ is constant in all recursive calls, there are $\Theta(2^n n)$ different subproblems, and each subproblem depends on at most $n$ others. Thus, the dynamic programming algorithm runs in $O(2^n n^2)$ time.

Or does it?!

The standard integer RAM model allows constant-time manipulation of integers with $O(\log n)$ bits, but at least for arithmetic and logical operations, larger integers must be broken into word-sized chunks. (Otherwise, strange things can happen.) Is this not also true of access to longer memory addresses? If an algorithm uses superpolynomial space, is it reasonable to assume that memory accesses require only constant time?

For the Bellman-Held-Karp algorithm in particular, the algorithm must transform the description of the subset $X$ into the description of the subset $X\setminus\{v\}$, for each $v$, in order to access the memoization table. If the subsets are represented by integers, these integers require $n$ bits and therefore cannot be manipulated in constant time; if they are not represented by integers, their representation cannot be used directly as an index into the memoization table.

So: What is the actual asymptotic running time of the Bellman-Held-Karp algorithm?

$\endgroup$
  • $\begingroup$ Your "strange things" link is broken. $\endgroup$ – Tyson Williams Sep 12 '11 at 15:27
  • $\begingroup$ I fixed the link. $\endgroup$ – Jeffε Sep 13 '11 at 12:00
12
$\begingroup$

This is less of a mathematical answer than a philosophical one, but I prefer to think of a RAM model that allows constant-time manipulation of integers with some number B of bits that is unknown but at least as large as $\log_2 S$, where S is the amount of space that the algorithm requires. Because, if the integers weren't that big, how could you even address your memory? For polynomial time and space algorithms it's the same as O(log n) bits, but for exponential space algorithms it avoids the problem.

Of course, if S exceeds the amount of memory you actually have, your algorithm won't run at all. Or, it will run by paging information into and out of memory and you should be using a memory hierarchy model instead of the RAM model.

$\endgroup$
  • $\begingroup$ I'm used to the idea that the machine model should depend on the input size $n$, but there's something a little wonky about letting the machine model depend on the algorithm. Do you really want to let your machine solve any problem in PSPACE in constant time, as long as you're already using exponential space? $\endgroup$ – Jeffε Dec 10 '10 at 4:47
  • 3
    $\begingroup$ To me it's less a question of making the model vary depending on the algorithm, and more a question of having a model that is fixed but not capable of running all algorithms (because it runs out of space). That doesn't sound so different from real computers, to me. $\endgroup$ – David Eppstein Dec 12 '10 at 23:29
  • 1
    $\begingroup$ I am not convinced by David's answer. There are two issues here. One is theoretical, the other practical. In the theoretical setting it is more natural to be precise about the model and analyze the running time appropriately. In the practical setting it is not easy to know whether one would actually run out of memory on any particular instance because of various optimizations that one can do (and do partial memoization etc), however, when implementing the algorithm we will have to deal with how we store the sets and index into them. The above model does not help in this regard. $\endgroup$ – Chandra Chekuri Sep 13 '11 at 19:22
8
$\begingroup$

There is a discussion of this issue in the recent book by Fedor V. Fomin and Dieter Kratsch "Exact Exponential Algorithms" where they specify the running time in the unit-cost RAM model and the log-cost RAM model ($W$ - the maximum distance between the cities and $f(n)=\mathcal{O}^{\ast}(g(n))$ if $f(n)=\mathcal{O}(g(n)poly(n))$):

$\mathcal{O}^{\ast}(2^n)$ and $2^n\log Wn^{\mathcal{O}(1)}$ (note, $2^n\log Wn^{\mathcal{O}(1)}\notin\mathcal{O}^{\ast}(2^n)$ ), respectively.

$\endgroup$
  • 1
    $\begingroup$ So they dodge the issue by hiding the polynomial factor. I want to know what the polynomial factor is! $\endgroup$ – Jeffε Dec 9 '10 at 14:33
  • 3
    $\begingroup$ They assume that the polynomial factor is $n^2$ (see the link in my comment). $\endgroup$ – Oleksandr Bondarenko Dec 9 '10 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.