Travelling Salesman Problem (TSP) Courses and Certifications

Reducible

The Traveling Salesman Problem - When Good Enough Beats Perfect

Explore heuristic approaches and optimization techniques for the Traveling Salesman Problem, including nearest neighbor, greedy, Christofides, local search, simulated annealing, and ant colony optimization.

• YouTube
• 30 minutes
• On-Demand
• Free Video

Simons Institute

A Slightly Improved Approximation Algorithm for Metric TSP

Explore an improved approximation algorithm for the Metric Traveling Salesman Problem, focusing on 2-uniform spanning trees and probabilistic techniques in algorithm design.

• YouTube
• 46 minutes
• On-Demand
• Free Video

Association for Computing Machinery (ACM)

Reducing Path TSP to TSP

Learn about reducing Path TSP to TSP, exploring canonical ideas, large distances, special cases, and practical examples in this concise algorithmic exploration.

• YouTube
• 25 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

A 1.5-Approximation for Path TSP

Explores a 1.5-approximation algorithm for the Metric Path Traveling Salesman Problem, introducing novel techniques to handle larger s-t cuts and achieve a simplified approach matching Christofides' TSP algorithm.

• YouTube
• 1 hour 16 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

The Approximation Ratio of the k-Opt Heuristic for Euclidean TSP

Explore the k-Opt heuristic's approximation ratio for Euclidean TSP, improving upper bounds and providing new lower bounds for k ≥ 3, applicable to various p-norms.

• YouTube
• 32 minutes
• On-Demand
• Free Video

Hausdorff Center for Mathematics

Matthias Mnich - Time- and Space-Optimal Algorithms for the Many-Visits TSP

Optimizing algorithms for the many-visits TSP problem, improving time and space complexity while maintaining logarithmic dependence on tour length. Discusses applications and compares with previous work.

• YouTube
• 28 minutes
• On-Demand
• Free Video

Institute for Pure & Applied Mathematics (IPAM)

The Transformer Network for the Traveling Salesman Problem

Explore how Transformer networks can tackle the Traveling Salesman Problem, improving upon existing heuristics with promising results for combinatorial optimization challenges.

• YouTube
• 30 minutes
• On-Demand
• Free Video