Algorithms for NP-Hard Problems (Section 21.1: The Bellman-Held-Karp Algorithm for TSP) [Part 2/2]
Tim Roughgarden Lectures · 15:48
The Held–Karp / Bellman dynamic program for TSP follows from a structural fact: a min-cost path from vertex 1 to \(J\) that visits every vertex once is completely determined once you name the penultimate vertex \(K\),...