TSP Approximation Algorithms | Efficient Solutions to 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: https://youtu.be/Rc6SIG2Q4y0 ► Prim's Algorithm, https://youtu.be/MaaSoZUEoos ► Depth First Search, https://youtu.be/tlPuVe5Otio Some of my other related graph videos: ► Dijkstras Intro https://youtu.be/U9Raj6rAqqs ► Dijkstras on Directed Graph https://youtu.be/k1kLCB7AZbM ► Bellman-Ford https://youtu.be/dp-Ortfx1f4 ► Bellman-Ford Example https://youtu.be/vzBtJOdoRy8 ► Floyd-Warshall https://youtu.be/KQ9zlKZ5Rzc ► Floyd-Warshall on Undirected Graph https://youtu.be/B06q2yjr-Cc ► Breadth First Search https://youtu.be/E_V71Ejz3f4