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