Algorithms for NP-Hard Problems (Section 19.1: The Algorithmic Mystery of MST vs. TSP)
Tim Roughgarden Lectures · 16:19
MST and the traveling salesman problem look almost identical as graph optimization tasks, but MST has near-linear exact algorithms while TSP has no known polynomial-time algorithm and is the canonical NP-hard example...