TSP Approximation Algorithms | Solving the Traveling Salesman Problem

This video explores the Traveling Salesman Problem, and explains two approximation algorithms for finding a solution in polynomial time. The first method explained is a 2-approximation that uses a minimum spanning tree (MST) and depth first search (DFS). The second method is Christofides' algorithm, which combines perfect matching with a minimum spanning tree. TSP is a classic NP-Hard problem.

I recommend you first watch the following videos on MSTs and DFS, which I reference in this video:
► Kruskal's Algorithm:    • Kruskals Algorithm for Minimum Spanning Trees  
► Prim's Algorithm,    • Prims Algorithm for Minimum Spanning Trees  
► Depth First Search,    • Depth-First Search Algorithm DFS  

Some of my other related graph videos:
► Dijkstras Intro    • Dijkstras Algorithm for Single-Source Shor...  
► Dijkstras on Directed Graph    • Dijkstras Algorithm Directed Graph Example  
► Bellman-Ford    • Bellman-Ford Single-Source Shortest-Path a...  
► Bellman-Ford Example    • Bellman Ford Algorithm Example  
► Floyd-Warshall    • Floyd Warshall Graph Traversal Algorithm: ...  
► Floyd-Warshall on Undirected Graph    • Floyd Warshall Algorithm on Undirected Gra...  
► Breadth First Search    • Breadth First Search - BFS algorithm