Held-Karp Algorithm

The Held-Karp algorithm is a dynamic programming algorithm for finding a minimum-weight Hamiltonian cycle, and therefore an exact solution of the traveling salesman problem. Let the vertices of a complete weighted graph be 1, 2, ..., , let be the weight of the graph edge joining and , and fix vertex 1 as the starting point. For a nonempty subset and , define to be the minimum weight of a path that starts at 1, visits precisely the vertices in , and ends at .

For , the initial values are

$D({j},j)=c_(1j).$

(1)

For , the recurrence relation is

$D(S,j)=min_(i in S\{j})[D(S\{j},i)+c_(ij)].$

(2)

The minimum tour length is then

$L=min_(j in {2,...,n})[D({2,...,n},j)+c_(j1)].$

(3)

Evaluating the subsets in increasing order of size gives states, each of which examines at most possible preceding vertices. The resulting running time is , and storing the full table and one minimizing predecessor per state requires space. Following the predecessors reconstructs a minimum tour. Bellman (1962) published a closely related dynamic programming treatment of the traveling salesman problem.

References

Bellman, R. "Dynamic Programming Treatment of the Travelling Salesman Problem." J. Assoc. Comput. Mach. 9, 61-63, 1962. https://doi.org/10.1145/321105.321111.

Held, M. and Karp, R. M. "A Dynamic Programming Approach to Sequencing Problems." J. Soc. Indust. Appl. Math. 10, 196-210, 1962. https://doi.org/10.1137/0110015.

Held-Karp Algorithm

See also

Explore with Wolfram|Alpha

References

Cite this as:

Subject classifications