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:

Some of my other related graph videos:

[daanvandenberg]

I think you're doing great work in making these algorithms widely understandable for a broad class of people. Might use your video's sometime in a course for my students or so.

[kushagragupta]

that plane crash effect was amazing!!😂😂👍👍

[lorossi]

Jump to 8:48 to see what happens when you don't go the optimal route and the airplane runs out of fuel

[ZapOKill]

and now the trivial part of solving min-weight perfect match

[andrewhudson]

A great description of a hard problem.

[daanvandenberg]

I think there might be a few slight mistakes in the OPT <= MSTtour <= 2*MST explanation. The optimal solution can never be one MST because such a tour could always remove the longest edge, obtaining a shorter MST. Furthermore, I think MSTtour < 2*MST, because you always need at least one shortcut to close the MST into a tour. So I guess it should be MST < OPT <= MSTtour < 2*MST. Please review at your convenience.

[darbyl]

What algorithm allows a node to be visited more than once? The one-time restriction does not always give the optimal route (in real life).

[ashrafyawar]

@Joe James, could you help me out on generalized version of christofies algorithm ?

[christopherlperezcruz]

Doing Hungarian Method on excel. Using row and column reduction then penalty for each 0. When the penalties are equal I end up marking both bc I can't figure how to choose. Will this affect my optimality?

[chinitatuntun]

Thanks for the Traveling Sales PERSON problem! :)

[srishtiarora]

how can we add edges of M to T? Won't it change the original graph?

[dekisugiNohara]

Why the plane crash, I thought it was an Ad.

[randy]

Didn't we violate the rule of not visiting a node more than once?

[amerm.alnajada]

hello I found the exact solution of this problem . How can I send it to win a prize and get the right of possession?