Opening Approximation Algorithms: Traveling Salesman Problem
Approximation Algorithms: Traveling Salesman Problem
- Length
- 32 min
- Level
- Undergraduate
- Recorded
- MIT2016
Chapter 1 of 5: Before the lecture
Shortcuts a depth-first walk of a minimum spanning tree into a tour, then reaches with Christofides' matching.
The metric traveling salesman problem admits constant-factor approximations once the triangle inequality holds, though general TSP and its constant approximations are NP-hard. In this recitation for MIT 6.046J, Biswas builds a minimum spanning tree and walks it by depth-first search. The triangle inequality lets the walk skip repeated vertices, giving a tour at most twice the optimal length. Restricting a Hamiltonian cycle to a vertex subset keeps its cost bound, which ties perfect matchings on that subset to the optimal tour. Christofides' algorithm then matches the even number of odd-degree tree vertices and shortcuts the Eulerian circuit into a -approximation.
The metric traveling salesman problem admits constant-factor approximations once the triangle inequality holds, though general TSP and its constant approximations are NP-hard. In this recitation for MIT 6.046J, Biswas builds a minimum spanning tree and walks it by depth-first search. The triangle inequality lets the walk skip repeated vertices, giving a tour at most twice the optimal length. Restricting a Hamiltonian cycle to a vertex subset keeps its cost bound, which ties perfect matchings on that subset to the optimal tour. Christofides' algorithm then matches the even number of odd-degree tree vertices and shortcuts the Eulerian circuit into a -approximation.

This lecture
Lecture 21 of 27 of Design and Analysis of Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in