<p>Addendum to below, clarifying the $k(k-1)$ terms:</p>

<p>So, if you examine the terms in the expression, you can envision (as analogy) the $n-1 \choose k$ term is an enumeration of all binary strings containing $k$ 1's that have a 1 in the first position. In other words, we let each position in the binary string represent the choice of whether a given one of the $n$ cities in the problem are in the exact subset we are considering at the time. So, for 5 cities, 10101 corresponds to the subset {1,3,5}.</p>

<p>Thus, to compute across all subsets of {1,...,$n$}, we simply count through each binary subset (i.e. count through binary strings) of size=2 (i.e. binary strings of size $n$ that contain two 1's), then size=3, then size=4, ...then size=n. (Note that the size=1 subset must contain only the first city, and thus it's irrelevant to compute its partial distance, since the distance from 1 -> all other cities in the subset -> 1 is exactly 0.)</p>

<p>At each subset with $k$ cities, we have to consider up to $k-1$ candidate-optimal, partial paths. Specifically, the optimal, total path could conceivably traverse through the given subset and end up on any of the $k-1$ cities, excluding the first city. Then, for each such candidate sub-path, we compute the optimal tour up to that point as the minimum of any of the previous, size=$k-1$ sub-paths plus the distance from the terminal city for that sub-path to the terminal city for the current candidate sub-path. This gives $(k-1)(k-2)$ such comparisons that we must make. The discrepancy between my $(k-1)(k-2)$ term, and the $k(k-1)$ term in the analysis linked is a notational difference (I would sum over a different range, given my definition of $k$ than they did). At the very least, however, it should illustrate the quadratic-order complexity of that term.</p>

<hr>

<p>How interesting -- I just finished coding this exact algorithm up in C++ a few minutes ago. (So forgive the tangent from pure theory into a little practical discussion. :))</p>

<p>It costs $O(2^n n^2)$ time and $O(2^n n)$ space -- at least under my implementation. Practically speaking though, when your space requirements grow that fast, they become way more painful than the time requirements. For instance, on my PC (with 4 GB of RAM), I can solve instances with up to 24 cities -- any more than that, and I run out of memory.</p>

<p>Of course, I could just be a bad programmer, and you might be able to do better than me in practice. :)</p>

<p>Edit: A little more specifics on one detail of your question: The $k(k-1)$ term comes from the fact that you have to, in the worst case, calculate the partial, optimal distance from the previous subsets (there are at most $n$ of them; note that $k$ is summed over $n$ in the analysis you linked) to the current one. This requires, again in the worst case, $O(k)$ comparisons with subsets of size $k-1$ for a total of $O(k^2)$.</p>

<p>Also, if my explanation wasn't clear enough, here are some nice lecture notes of Vazirani's (<a href="http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf">PDF</a>). Scroll down to P. 188 for a discussion of TSP, including an analysis of Held-Karp.</p>

CC BY-SA 2.5
2010-12-06T04:01:09.480Z
Oh, of course! I feel silly thinking about that now; I'll update my answer. I'd actually heard that exact comment before, and just passed it on without thinking about it. And yeah -- writing to a file/reading from a file will let you go effectively go arbitrarily high on numbers of cities. ...it's also a pain not worth worrying about unless you're trying to solve TSP instances for a real purpose. Mine was decidedly not for a practical purpose. ;)
Daniel Apon
CC BY-SA 2.5
2010-12-06T04:20:39.370Z
Time to implement the Bjorklund algorithm :)
Suresh Venkat
CC BY-SA 2.5
2010-12-06T05:20:30.153Z
@Suresh: Good idea!
Daniel Apon
CC BY-SA 2.5
2010-12-06T17:27:37.180Z
@Daniel Apon Could you, please, make precise why we need comparisons when calculating "the partial, optimal distance"?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-07T02:12:03.813Z
@Oleksandr: Sure, I'll add it to the top of my answer.
Daniel Apon
CC BY-SA 2.5
2010-12-07T10:21:31.720Z
@David: Do you compare objective function values for tours? As I understand we need $(k-2)$ comaprisons for each one of $(k-1)$-subsets, but why so many comparisons? If we precomputed $(k-1)$ objective function values then it takes linear time to compute minimum. Where do I make a mistake?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-07T18:57:08.457Z
@Oleksandr: For a given *unordered* subset, you need to compute the minimums for each candidate path ending at each city in that subset (except for City 1). There are $O(2^n)$ such subsets, for each subset you need to compute $k$ values, and - yes, you are correct - the computation of each of those values takes linear time. In other words, you're solving $O(n2^n)$ sub-problems, each taking linear time to solve.
Daniel Apon
CC BY-SA 2.5
2010-12-07T18:59:12.510Z
You could think of it this way: Why are there $k-1$ previous candidate paths/distances to compare against? (Answer: Because you computed that many for a single previous subset in a previous computation! And each of those computations took linear time as well.)
Daniel Apon
CC BY-SA 2.5
2010-12-07T19:11:04.247Z
@Daniel: I think that I understand your point. Thanks to your last comment.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-08T04:25:21.897Z
@Oleksandr: Good! I'm glad to hear and glad to help.
Daniel Apon
CC BY-SA 2.5
2010-12-06T03:39:37.843Z
2010-12-07T02:34:39.503Z
2010-12-07T02:34:39.503Z
Daniel Apon
<h1>Main note</h1>
<p>It's important to note that we compute and store not<br />
&quot;distance of optimal path for <code>combination of k cities</code>&quot;<br />
but<br />
&quot;distance of optimal path for <code>combination of k cities</code> <strong>AND</strong> for <code>end-point city from this combination</code>&quot;.<br />
Understanding it will help with meaning of first two multipliers in following formula.</p>
<h2>First phase</h2>
<p>The number of operations in the first phase is:
<span class="math-container">$$
\displaystyle
\sum_{k&gt;=2}
\underbrace{
\binom{n-1}{k-1}
}_{\substack{
\text{choose city combination} \\
\text{of size = $k-1$}}}
\cdot 
\underbrace{
(k-1) 
}_{\substack{
\text{choose city to be the last}
\\
\text{from $k-1$ cities}
\\
\text{in chosen combination}
}
}
\cdot 
\underbrace{
((n-1)-(k-1))
}_{
\substack{
\text{choose city}
\\
\text{that is not in chosen combination}
\\
\text{to add to path}
}
}
$$</span></p>
<p>Missing superscript in sum means <code>for all k&gt;=2 that is valid for binomial coefficient</code>.
So the last valid not null term of sum will be for <span class="math-container">$k=n-1$</span>
<span class="math-container">$$
\binom{n-1}{n-2} \cdot (n-2) \cdot 1
$$</span>
It means that our sum doesn`t capture last choices of city to connect to the first city. There are <span class="math-container">$n-1$</span> cities to connect to the first city. So finally we will add this term to the sum.</p>
<p>Let transform formula to form that you provide that is also on
<a href="https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm#Dynamic_programming_approach" rel="nofollow noreferrer">Held-Karp Wikipedia page</a>.</p>
<p><span class="math-container">$$
\displaystyle
\sum_{k&gt;=2} \binom{n-1}{k-1} \cdot (k-1) \cdot ((n-1)-(k-1))=
\sum_{k&gt;=2} \frac{(n-1)!}{(k-1)!(n-k)!} \cdot (k-1) \cdot (n-k)=
\sum_{k&gt;=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1)=
\sum_{k&gt;=2} \binom{n-1}{k} \cdot k \cdot (k-1)
$$</span>
Manipulating binomial coefficients leads to:
<span class="math-container">$$
\displaystyle
\sum_{k&gt;=2} \binom{n-1}{k} \cdot k \cdot (k-1) =
\sum_{k&gt;=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1) =
\sum_{k&gt;=2} \frac{(n-3)!}{(k-2)!(n-3-(k-2))!} \cdot (n-1) \cdot (n-2)=
(n-1) \cdot (n-2)\sum_{k&gt;=2} \binom{n-3}{k-2}=(n-1) \cdot (n-2) \cdot 2^{n-3}
$$</span>
So the number of operations in the first phase is <span class="math-container">$(n-1) \cdot (n-2) \cdot 2^{n-3}+(n-1)$</span></p>
<h2>Second phase</h2>
<p>Second phase is restoring optimal path by marks we have made in the first phase simultaneously with computing distances.</p>
<p>For each optimal path &quot;for <code>combination of k cities</code> <strong>AND</strong> for <code>end-point city from this combination</code>&quot; we have saved the second-to-last city.</p>
<p>To backtrack optimal path we need to ask some data structure to return the second-to-last city &quot;for <code>combination of k cities</code> <strong>AND</strong> for <code>end-point city from this combination</code>&quot;.
So this data structure must be something like<br />
<code>Map&lt;combination of k cities, Map&lt;last city, second-to-last city&gt;&gt;</code>.
As index of <code>combination of k cities</code> we can use, for example, <code>binary_string[city id]=1 if city id is in combination</code> . So we need to look at all elements of <code>combination of k cities</code> to identify combination and index our data structure. This gives us the number of operations for the second phase:
<span class="math-container">$$
\displaystyle
\sum_{k&gt;=2}^{n-1} k = \frac{(n)(n-1)}{2} - 1
$$</span></p>

CC BY-SA 4.0
2018-12-09T20:10:09.613Z
2018-12-09T20:10:09.613Z
2020-06-17T09:38:08.363Z
dimathe47
<p>When I looked through &quot;A Dynamic Programming Approach to Sequencing Problems&quot; by Michael Held and Richard M. Karp<sup>1</sup>, I came up with the following question:
why the complexity of their algorithm for TSP is <span class="math-container">$(\sum_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1)$</span> (p. 199), I mean where do they take the factor <span class="math-container">$k$</span>? If I understood correctly <span class="math-container">$k-1$</span> means the number of additions for each subset of cities. Then why each addition operation is coupled with unknown to me <span class="math-container">$k$</span> operations? I suppose it is connected somehow to taking minimum, but computing minimum doesn't seem to require such many operations.</p>
<p>Dynamic programming algorithm by Held and Karp and independently Bellman runs as follows:
for each pair <span class="math-container">$(S,c_i)$</span>, meaning a path going through <span class="math-container">$c_1$</span>, all the elements of <span class="math-container">$S$</span> and terminating at <span class="math-container">$c_i$</span> compute</p>
<p><span class="math-container">$OPT[S,c_i]=min\{OPT[S\setminus\{c_i\},c_j]+d(c_j,c_i):c_j\in S\setminus\{c_i\}\},$</span></p>
<p>where <span class="math-container">$d(c_j,c_i)$</span> means the distance between cities <span class="math-container">$c_j$</span> and <span class="math-container">$c_i$</span>. Then in the formula from the paper <span class="math-container">$k$</span> means the size of <span class="math-container">$S$</span>.</p>
<p><sup>1</sup><em>Held, Michael; Karp, Richard M.</em>, <a href="https://scholar.google.com/scholar?hl=en&amp;q=held+karp+dynamic+approach+sequencing+problems" rel="nofollow noreferrer"><strong>A dynamic programming approach to sequencing problems</strong></a>, J. Soc. Ind. Appl. Math. 10, 196-210 (1962). DOI: <a href="http://dx.doi.org/10.1137/0110015" rel="nofollow noreferrer">10.1137/0110015</a>, <a href="https://www.jstor.org/stable/2098806" rel="nofollow noreferrer">JSTOR</a>. <a href="https://zbmath.org/?q=an:0106.14103" rel="nofollow noreferrer">ZBL0106.14103</a>, <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=139493" rel="nofollow noreferrer">MR139493</a>.</p>

<ds.algorithms><tsp><exp-time-algorithms>
Time complexity of Held-Karp algorithm for TSP
Oleksandr Bondarenko
# Time complexity of Held-Karp algorithm for TSP

(Asked by: username_0 on 2010-12-06)

When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp1, I came up with the following question:
why the complexity of their algorithm for TSP is $(\sum\_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1)$ (p. 199), I mean where do they take the factor $k$? If I understood correctly $k-1$ means the number of additions for each subset of cities. Then why each addition operation is coupled with unknown to me $k$ operations? I suppose it is connected somehow to taking minimum, but computing minimum doesn't seem to require such many operations.

Dynamic programming algorithm by Held and Karp and independently Bellman runs as follows:
for each pair $(S,c\_i)$, meaning a path going through $c\_1$, all the elements of $S$ and terminating at $c\_i$ compute

$OPT[S,c\_i]=min\{OPT[S\setminus\{c\_i\},c\_j]+d(c\_j,c\_i):c\_j\in S\setminus\{c\_i\}\},$

where $d(c\_j,c\_i)$ means the distance between cities $c\_j$ and $c\_i$. Then in the formula from the paper $k$ means the size of $S$.

1*Held, Michael; Karp, Richard M.*, [**A dynamic programming approach to sequencing problems**](https://scholar.google.com/scholar?hl=en&q=held+karp+dynamic+approach+sequencing+problems), J. Soc. Ind. Appl. Math. 10, 196-210 (1962). DOI: [10.1137/0110015](http://dx.doi.org/10.1137/0110015), [JSTOR](https://www.jstor.org/stable/2098806). [ZBL0106.14103](https://zbmath.org/?q=an:0106.14103), [MR139493](https://mathscinet.ams.org/mathscinet-getitem?mr=139493).

**Tags:** ds.algorithms, tsp, exp-time-algorithms

---

## 2 answers

### Answer by username_1 on 2010-12-06. Score: 5 | Accepted answer

Addendum to below, clarifying the $k(k-1)$ terms:

So, if you examine the terms in the expression, you can envision (as analogy) the $n-1 \choose k$ term is an enumeration of all binary strings containing $k$ 1's that have a 1 in the first position. In other words, we let each position in the binary string represent the choice of whether a given one of the $n$ cities in the problem are in the exact subset we are considering at the time. So, for 5 cities, 10101 corresponds to the subset {1,3,5}.

Thus, to compute across all subsets of {1,...,$n$}, we simply count through each binary subset (i.e. count through binary strings) of size=2 (i.e. binary strings of size $n$ that contain two 1's), then size=3, then size=4, ...then size=n. (Note that the size=1 subset must contain only the first city, and thus it's irrelevant to compute its partial distance, since the distance from 1 -> all other cities in the subset -> 1 is exactly 0.)

At each subset with $k$ cities, we have to consider up to $k-1$ candidate-optimal, partial paths. Specifically, the optimal, total path could conceivably traverse through the given subset and end up on any of the $k-1$ cities, excluding the first city. Then, for each such candidate sub-path, we compute the optimal tour up to that point as the minimum of any of the previous, size=$k-1$ sub-paths plus the distance from the terminal city for that sub-path to the terminal city for the current candidate sub-path. This gives $(k-1)(k-2)$ such comparisons that we must make. The discrepancy between my $(k-1)(k-2)$ term, and the $k(k-1)$ term in the analysis linked is a notational difference (I would sum over a different range, given my definition of $k$ than they did). At the very least, however, it should illustrate the quadratic-order complexity of that term.

---

How interesting -- I just finished coding this exact algorithm up in C++ a few minutes ago. (So forgive the tangent from pure theory into a little practical discussion. :))

It costs $O(2^n n^2)$ time and $O(2^n n)$ space -- at least under my implementation. Practically speaking though, when your space requirements grow that fast, they become way more painful than the time requirements. For instance, on my PC (with 4 GB of RAM), I can solve instances with up to 24 cities -- any more than that, and I run out of memory.

Of course, I could just be a bad programmer, and you might be able to do better than me in practice. :)

Edit: A little more specifics on one detail of your question: The $k(k-1)$ term comes from the fact that you have to, in the worst case, calculate the partial, optimal distance from the previous subsets (there are at most $n$ of them; note that $k$ is summed over $n$ in the analysis you linked) to the current one. This requires, again in the worst case, $O(k)$ comparisons with subsets of size $k-1$ for a total of $O(k^2)$.

Also, if my explanation wasn't clear enough, here are some nice lecture notes of Vazirani's ([PDF](http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf)). Scroll down to P. 188 for a discussion of TSP, including an analysis of Held-Karp.

> **Comments:**
> **username_1**: Oh, of course! I feel silly thinking about that now; I'll update my answer. I'd actually heard that exact comment before, and just passed it on without thinking about it. And yeah -- writing to a file/reading from a file will let you go effectively go arbitrarily high on numbers of cities. ...it's also a pain not worth worrying about unless you're trying to solve TSP instances for a real purpose. Mine was decidedly not for a practical purpose. ;)  
> **username_2**: Time to implement the Bjorklund algorithm :)  
> **username_1**: @Suresh: Good idea!  
> **username_0**: @Daniel Apon Could you, please, make precise why we need comparisons when calculating "the partial, optimal distance"?  
> **username_1**: @Oleksandr: Sure, I'll add it to the top of my answer.  
> **username_0**: @David: Do you compare objective function values for tours? As I understand we need $(k-2)$ comaprisons for each one of $(k-1)$-subsets, but why so many comparisons? If we precomputed $(k-1)$ objective function values then it takes linear time to compute minimum. Where do I make a mistake?  
> **username_1**: @Oleksandr: For a given *unordered* subset, you need to compute the minimums for each candidate path ending at each city in that subset (except for City 1). There are $O(2^n)$ such subsets, for each subset you need to compute $k$ values, and - yes, you are correct - the computation of each of those values takes linear time. In other words, you're solving $O(n2^n)$ sub-problems, each taking linear time to solve.  
> **username_1**: You could think of it this way: Why are there $k-1$ previous candidate paths/distances to compare against? (Answer: Because you computed that many for a single previous subset in a previous computation! And each of those computations took linear time as well.)  
> **username_0**: @Daniel: I think that I understand your point. Thanks to your last comment.  
> **username_1**: @Oleksandr: Good! I'm glad to hear and glad to help.  

---

### Answer by username_3 on 2018-12-09. Score: 2

# Main note

It's important to note that we compute and store not  
"distance of optimal path for `combination of k cities`"  
but  
"distance of optimal path for `combination of k cities` **AND** for `end-point city from this combination`".  
Understanding it will help with meaning of first two multipliers in following formula.

## First phase

The number of operations in the first phase is:
$$
\displaystyle
\sum\_{k>=2}
\underbrace{
\binom{n-1}{k-1}
}\_{\substack{
\text{choose city combination} \\
\text{of size = $k-1$}}}
\cdot
\underbrace{
(k-1)
}\_{\substack{
\text{choose city to be the last}
\\
\text{from $k-1$ cities}
\\
\text{in chosen combination}
}
}
\cdot
\underbrace{
((n-1)-(k-1))
}\_{
\substack{
\text{choose city}
\\
\text{that is not in chosen combination}
\\
\text{to add to path}
}
}
$$

Missing superscript in sum means `for all k>=2 that is valid for binomial coefficient`.
So the last valid not null term of sum will be for $k=n-1$
$$
\binom{n-1}{n-2} \cdot (n-2) \cdot 1
$$
It means that our sum doesn`t capture last choices of city to connect to the first city. There are $n-1$ cities to connect to the first city. So finally we will add this term to the sum.

Let transform formula to form that you provide that is also on
[Held-Karp Wikipedia page](https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm#Dynamic_programming_approach).

$$
\displaystyle
\sum\_{k>=2} \binom{n-1}{k-1} \cdot (k-1) \cdot ((n-1)-(k-1))=
\sum\_{k>=2} \frac{(n-1)!}{(k-1)!(n-k)!} \cdot (k-1) \cdot (n-k)=
\sum\_{k>=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1)=
\sum\_{k>=2} \binom{n-1}{k} \cdot k \cdot (k-1)
$$
Manipulating binomial coefficients leads to:
$$
\displaystyle
\sum\_{k>=2} \binom{n-1}{k} \cdot k \cdot (k-1) =
\sum\_{k>=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1) =
\sum\_{k>=2} \frac{(n-3)!}{(k-2)!(n-3-(k-2))!} \cdot (n-1) \cdot (n-2)=
(n-1) \cdot (n-2)\sum\_{k>=2} \binom{n-3}{k-2}=(n-1) \cdot (n-2) \cdot 2^{n-3}
$$
So the number of operations in the first phase is $(n-1) \cdot (n-2) \cdot 2^{n-3}+(n-1)$

## Second phase

Second phase is restoring optimal path by marks we have made in the first phase simultaneously with computing distances.

For each optimal path "for `combination of k cities` **AND** for `end-point city from this combination`" we have saved the second-to-last city.

To backtrack optimal path we need to ask some data structure to return the second-to-last city "for `combination of k cities` **AND** for `end-point city from this combination`".
So this data structure must be something like  
`Map>`.
As index of `combination of k cities` we can use, for example, `binary_string[city id]=1 if city id is in combination` . So we need to look at all elements of `combination of k cities` to identify combination and index our data structure. This gives us the number of operations for the second phase:
$$
\displaystyle
\sum\_{k>=2}^{n-1} k = \frac{(n)(n-1)}{2} - 1
$$


---

